Introduction

Within the subject area of machine learning, gradient descent is perhaps the most well-known and commonly used iterative optimization method for finding the parameters that minimize error functions such as residual sum of squares for (\(L_1\)-regularized) linear regression, or negative log-likelihoods for logistic regression and neural networks.

However, there are a few alternative methods that may perform better than gradient descent in specific cases. For example:

In this notebook, we will be comparing coordinate and gradient descent in the bivariate function setting—functions only accepting two inputs. This comparison is aimed at understanding optimization methods more abstractly, rather than their applications to machine learning.

It is important to note that coordinate descent generally refers to the approach of minimizing a multivariate function by minimizing it in one direction or coordinate at a time (solving univariate optimization problems repeatedly). This means that it is possible to apply coordinate descent to both differentiable and derivative-free contexts3.

However, in this notebook, coordinate descent refers to gradient-based coordinate descent.

Setup

# Set working directory
setwd("~/Downloads/R/minimizers")

# Install dependencies
#install.packages("shiny")
#install.packages("plotly")
#install.packages("plyr")
#install.packages("ggplot2")
#install.packages("ggpubr")

# Require dependencies
require(shiny)
require(plotly)
require(plyr)
require(ggplot2)
require(ggpubr)

# Set seed for reproducibility
set.seed(9292)

Test functions

Comparison metrics will include benchmarks, number of iterations and convergence/divergence. These metrics will be used to test both optimization methods on two differentiable bivariate functions: the Six-hump camel function and the Peaks function.

Six-hump camel function

The Six-hump camel function is a test function used for investigating the performance of optimization algorithms.4

The function is defined by:

\[ F_1(x,y)=\left(4-2.1x^2+\frac{x^4}{3}\right)x^2+xy+4\left(y^2-1\right)y^2 \] Despite being well defined for all \((x,y)\in\mathbb{R}^2\), the focal point of this function is within the \(x,y\in[-6,6]\) region, where all of the turning points of the function lie. However, for visualization, this region can be made smaller: \(x\in[-2,2],\ y\in[-1,1]\).

# Import Six-hump camel function
source("functions/camel.R")

# Set input variable ranges
F1.x <- seq(-2, 2, length=100)
F1.y <- seq(-1, 1, length=100)
F1.z <- t(outer(F1.x, F1.y, F1))

# Display plot and contours
F1.plot <- plot_ly(x=F1.x, y=F1.y, z=F1.z, width=700, height=500) %>%
  add_surface(contours=list(z=list(show=TRUE, usecolormap=TRUE, highlightcolor="#ff0000", project=list(z=TRUE)))) %>%
  layout(scene=list(zaxis=list(range=c(-2,6)), aspectmode="manual", aspectratio=list(x=1, y=1, z=0.6)),
         title="Six-hump camel function (F1)")

div(F1.plot, align="center")

Minima

Type \(x\) \(y\) \(f(x,y)\)
Global \(0.089842\) \(-0.712656\) \(-1.031628453\)
Global \(-0.089842\) \(0.712656\) \(-1.031628453\)

Partial derivatives

The gradient vector \(\nabla F_1(x,y)\) for the Six-hump camel function consists of the following partial derivatives:

\[ \begin{align} \nabla F_1(x,y) &=\begin{pmatrix} \frac{\partial F_1}{\partial x}\\ \frac{\partial F_1}{\partial y} \end{pmatrix}\\ &=\begin{pmatrix} 2\left(x^5-4.2x^3+4x+0.5y\right) \\ x+16y^3-8y \end{pmatrix} \end{align} \]

The Peaks function

The Peaks function5 is a function often used to demonstrate 3D graphing software or libraries in MATLAB and other programming languages.

The function is defined by:

\[ \begin{align} F_2(x,y)&= 3(1-x)^2e^{-x^2-(y+1)^2}\\ &+10\left(\frac{1}{5}x-x^3-y^5\right)e^{-\left(x^2+y^2\right)}\\ &+\frac{1}{3}e^{-(x+1)^2-y^2} \end{align} \]

For optimization tests, this function is normally restricted to the \(x,y\in[-4,4]\) region, as this is where the extrema of the function lie. However, for visualization purposes, \([-3,3]\) is preferable for \(x\).

# Import Peaks function
source("functions/peaks.R")

# Set input variable ranges
F2.x <- seq(-3, 3, length=100)
F2.y <- seq(-3, 3, length=100)
F2.z <- t(outer(F2.x, F2.y, F2))

# Display plot and contours
F2.plot <- plot_ly(x=F2.x, y=F2.y, z=F2.z, width=700, height=500) %>%
  add_surface(contours=list(z=list(show=TRUE, usecolormap=TRUE, highlightcolor="#ff0000", project=list(z=TRUE)))) %>%
  layout(scene=list(aspectmode="manual", aspectratio=list(x=1, y=1, z=0.65)),
         title="Peaks function (F2)")

div(F2.plot, align="center")

Minima

Type \(x\) \(y\) \(f(x,y)\)
Global \(0.2282799999\) \(-1.6255310720\) \(-6.5511333326\)

Partial derivatives

The gradient vector \(\nabla F_2(x,y)\) for the Peaks function consists of the following partial derivatives:

\[ \begin{align} \nabla F_2(x,y) &=\begin{pmatrix} \frac{\partial F_2}{\partial x}\\ \frac{\partial F_2}{\partial y} \end{pmatrix}\\ &=\begin{pmatrix} -\frac{2}{3}e^{-\big(x^2 + 2 x + (y + 1)^2\big)} \Big( e^{2x+2y+1}\big( 30x^3-6x^2+30x(y^5-1)+3 \big) + 9e^{2x}\left( x^3-2x^2+1 \right) + (x+1)\left(-e^{2y}\right) \Big)\\ -\frac{2}{3}e^{-\big(x^2+2x+(y+1)^2\big)} \Big( 3ye^{2x+2y+1}\big( 10x^2-2x+5(2y^2-5)y^3 \big) + 9e^{2x}(1-x)^2(y+1) - ye^{2y} \Big) \end{pmatrix} \end{align} \]

These partial derivatives are far more complex than those of the Six-hump camel function. Since both of the optimization methods we are testing are gradient-based, it is likely that benchmarks for this test function will take significantly longer.

With complex derivatives such as these (or when the function is non-differentiable entirely), it is often more preferable to use derivative-free optimization methods6 such as the Nelder-Mead method7.

Optimization methods

Gradient descent

Gradient descent is a gradient-based iterative optimization method. Gradient descent works by iteratively updating the current position by taking a small step in the direction of steepest descent8.

\[ \mathbf{x}_{i+1} \leftarrow \mathbf{x}_i - \eta \nabla F(\mathbf{x}) \]

Where:

  • \(\eta\) is the learning rate for the algorithm—the size of the step taken on each iteration.
  • \(\nabla F(\mathbf{x})\) is the gradient vector of \(F(\mathbf{x})\), which represents the direction of steepest ascent.

With a bivariate function \(F(x,y)\), we can update the vector \(\begin{pmatrix}x \\ y\end{pmatrix}\) with:

\[ \begin{pmatrix} x \\ y \end{pmatrix} \leftarrow \begin{pmatrix} x \\ y \end{pmatrix} -\eta\begin{pmatrix} \frac{\partial F}{\partial x} \\ \frac{\partial F}{\partial y} \end{pmatrix} \] Choosing the learning rate \(\eta\) is a frequent problem in optimization—too large of a learning rate sometimes leads to divergence and missing the minimum due to having such large steps. Conversely, a very small learning rate will require many iterations to converge, which can be costly in terms of time and CPU/memory usage.

In order to ensure convergence, we will use a small learning rate.

# Set a small learning rate
rate <- 0.0475

It is also necessary to set a maximum number of iterations for iterative methods. In the event that the method diverges, it will still terminate execution. Likewise, if \(\eta\) is too small and too many iterations have passed without reaching a minimum, the method will stop.

In this case, the maximum number of iterations will be \(200\).

# Set maximum number of iterations
max_iterations <- 200

In this notebook, we will say that an optimization method converges to a minimum point \(\begin{pmatrix}x^* \\ y^*\end{pmatrix}\) if it reaches a point \(\begin{pmatrix}x \\ y\end{pmatrix}\) such that the Euclidean distance (\(L_2\) norm) between the two is less than some \(\epsilon\in\mathbb{R^+}\). In other words, if \(\begin{pmatrix}x \\ y\end{pmatrix}\) is in the \(\epsilon\)-neighbourhood of \(\begin{pmatrix}x^* \\ y^*\end{pmatrix}\): \[ \left|\left| \begin{pmatrix}x^* \\ y^*\end{pmatrix} - \begin{pmatrix}x \\ y\end{pmatrix} \right|\right|_2 < \epsilon\\ \]

# Set a small epsilon
epsilon <- 0.05

We define the gradient descent algorithm recursively as:

# Gradient descent (recursive implementation)
#
# Parameters:
#   x: The x-coordinate at the current position
#   y: The y-coordinate at the current position
#   FUN: The gradient vector for the function being optimized
#   iterations: The number of iterations (should start at 1)
#   minimum: The actual minimum of the function
#
# Returns:
#   A tuple consisting of (termination reason, iterations).
#
gradient.descent <- function(x, y, FUN, iterations, minimum) {
  # Check for maximum iterations
  if(iterations > max_iterations) return(c("Maximum iterations reached", iterations-1))
  # Check for convergence
  if(dist(rbind(c(x, y), minimum)) <= epsilon) return(c("Converged", iterations-1))

  # Add starting point to path if it is the first iteration
  if(iterations == 1) path[[1]] <<- c(x, y)

  # Make an update to the current position
  updated <- c(x, y) - rate * FUN(x, y)

  # Increment iterations and store updated position in `path` variable
  iterations <- iterations + 1
  path[[iterations]] <<- updated

  # Make updates recursively
  gradient.descent(updated[1], updated[2], FUN, iterations, minimum)
}

Where: path is a global variable that stores all of the intermediate vectors during the optimization process.

Testing on the Six-hump camel function

Before we start testing, we need a minimum of interest, along with a starting point for the optimization process:

# Minimum of interest
F1.minimum <- c(0.089842, -0.712656)

# Starting point
F1.start <- c(0.85, 0)

Additionally, we will need to initialize the path variable for keeping track of the updated vectors during the optimization process. This variable will be reused for other tests, so we will also define a reset function.

# Create an empty path vector
path <- vector("list", max_iterations)

# Reset function for the `path` variable
reset_path <- function() { path <<- vector("list", max_iterations) }

Running the gradient descent method (with benchmarking):

# Run timed gradient descent
F1.gradient.time <- proc.time()
F1.gradient.results <- gradient.descent(F1.start[1], F1.start[2], F1.d, 1, F1.minimum)
F1.gradient.time <- proc.time() - F1.gradient.time

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F1.gradient.contour <- plot_ly(x=~F1.x, y=~F1.y, z=F1.z, width=800, height=500,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F1.minimum[1], y=F1.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F1.start[1], y=F1.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=30, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F1.minimum[1], y=F1.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="GD optimization of the six-hump camel function (F1)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F1.gradient.contour, align="center")

Termination reason and number of iterations:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F1.gradient.results[1], F1.gradient.results[2]))
Termination reason: Converged
Number of iterations: 9

Benchmarking for these optimization methods will be done with the proc.time base function in R9. This function records the time taken for a specific action to finish execution, according three different time measures:

  1. user: The CPU time charged for the execution of user instructions of the calling process.
  2. system: The CPU time charged for execution by the system on behalf of the calling process.
  3. elapsed: The “real” elapsed time since the process was started.

Printing the proc_time result displays these measures in order:

print(F1.gradient.time)
   user  system elapsed 
  0.050   0.003   0.052

Testing on the Peaks function

Setting a minimum of interest, along with a starting point:

# Minimum of interest
F2.minimum <- c(0.228279999979237, -1.625531071954464)

# Starting point
F2.start <- c(1, -0.2)

Resetting the optimization path variable (path) and running the gradient descent method (with benchmarking):

# Resetting optimization path
reset_path()

# Run timed gradient descent
F2.gradient.time <- proc.time()
F2.gradient.results <- gradient.descent(F2.start[1], F2.start[2], F2.d, 1, F2.minimum)
F2.gradient.time <- proc.time() - F2.gradient.time

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F2.gradient.contour <- plot_ly(x=~F2.x, y=~F2.y, z=F2.z, width=700, height=600,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F2.minimum[1], y=F2.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F2.start[1], y=F2.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-5, ay=-40,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F2.minimum[1], y=F2.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="GD optimization of the peaks function (F2)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F2.gradient.contour, align="center")

Termination reason and number of iterations:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F2.gradient.results[1], F2.gradient.results[2]))
Termination reason: Converged
Number of iterations: 9

Benchmarks:

print(F2.gradient.time)
   user  system elapsed 
  0.081   0.003   0.083

Coordinate descent

Gradient-based coordinate descent is a similar method of optimization to gradient descent, as each iteration still updates the position by moving (by a step size \(\eta\)) in the direction of steepest descent.

However, the main difference with coordinate descent is that we optimize one coordinate at a time—essentially solving \(d\) univariate optimization problems (if the function \(F\) is \(d\)-variate). The optimization paths from these sub-problems are then combined to form a solution to the original optimization problem.

For a single coordinate \(i\), the iterative update formula is given by: \[ x_{i+1} \leftarrow x_i - \eta \frac{\partial}{\partial x_i}F(\mathbf{x}) \]

We define the coordinate descent algorithm recursively as:

# Coordinate descent (recursive implementation)
#
# Parameters:
#   x: The x-coordinate at the current position
#   y: The y-coordinate at the current position
#   fixed: Which coordinate remains fixed (1 -> x, 2 -> y) we optimize the non-fixed coordinate
#   FUN: The gradient vector for the function being optimized
#   iterations: The number of iterations (should start at 1)
#   minimum: The actual minimum of the function
#
# Returns:
#   A tuple consisting of (termination reason, iterations).
#
coordinate.descent <- function(x, y, fixed, FUN, iterations, minimum) {
  # Check for maximum iterations
  if(iterations > max_iterations) return(c("Maximum iterations reached", iterations-1))

  # Optimizing x coordinate
  if (fixed == 2) {
    # Check for convergence
    if(dist(rbind(x, minimum[1])) <= epsilon) return(c("Converged", iterations-1))

    # Add starting coordinate to path if it is the first iteration
    if(iterations == 1) path[[1]] <<- x

    # Make an update to the current coordinate
    updated.x <- x - rate * FUN(x, y)[1]

    # Increment iterations and store updated position in `path` variable
    iterations <- iterations + 1
    path[[iterations]] <<- updated.x

    # Make updates recursively
    coordinate.descent(updated.x, y, fixed=2, FUN, iterations, minimum)
  }

  # Optimizing y coordinate
  else if (fixed == 1) {
    # Check for convergence
    if(dist(rbind(y, minimum[2])) <= epsilon) return(c("Converged", iterations-1))

    # Add starting coordinate to path if it is the first iteration
    if(iterations == 1) path[[1]] <<- y

    # Make an update to the current coordinate
    updated.y <- y - rate * FUN(x, y)[2]

    # Increment iterations and store updated position in `path` variable
    iterations <- iterations + 1
    path[[iterations]] <<- updated.y

    # Make updates recursively
    coordinate.descent(x, updated.y, fixed=1, FUN, iterations, minimum)
  }
}

Testing on the Six-hump camel function

\(x\)-coordinate optimization

Optimizing the \(x\)-coordinate:

# Reset optimization path
reset_path()

# Run timed x-coordinate descent
F1.coordinate.x.time <- proc.time()
F1.coordinate.x.results <- coordinate.descent(F1.start[1], F1.start[2], 2, F1.d, 1, F1.minimum)
F1.coordinate.x.time <- proc.time() - F1.coordinate.x.time

# Trucate NULLs in optimization path list
F1.coordinate.x.path <- Filter(Negate(is.null), path)

Termination reason and number of iterations for \(x\)-coordinate optimization:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F1.coordinate.x.results[1], F1.coordinate.x.results[2]))
Termination reason: Converged
Number of iterations: 6

Benchmarks for \(x\)-coordinate optimization:

print(F1.coordinate.x.time)
   user  system elapsed 
  0.053   0.002   0.055
\(y\)-coordinate optimization

Optimizing the \(y\)-coordinate:

# Reset optimization path from x coordinate
reset_path()

# Run timed y-coordinate descent
F1.coordinate.y.time <- proc.time()
F1.coordinate.y.results <- coordinate.descent(F1.start[1], F1.start[2], 1, F1.d, 1, F1.minimum)
F1.coordinate.y.time <- proc.time() - F1.coordinate.y.time

# Trucate NULLs in optimization path list
F1.coordinate.y.path <- Filter(Negate(is.null), path)

Termination reason and number of iterations for \(y\)-coordinate optimization:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F1.coordinate.y.results[1], F1.coordinate.y.results[2]))
Termination reason: Converged
Number of iterations: 7

Benchmarks for \(y\)-coordinate optimization:

print(F1.coordinate.y.time)
   user  system elapsed 
  0.038   0.002   0.039
Solving the original optimization problem

We now have to combine the optimization paths of each coordinate in order to form a single optimization path for the original problem. We do this by interleaving elements from each coordinate’s path—however, we must account for the fact that one coordinate may converge faster than another (if at all). In this case, we extend the optimization path of the coordinate that converged in fewer iterations, by its last entry until its length is the same as that of the other coordinate’s optimization path.

# Calculate the difference between the number of iterations of both coordinate's optimization paths
path_difference <- length(F1.coordinate.x.path) - length(F1.coordinate.y.path)

if (path_difference > 0) {
  # If the x-coordinate's optimization path had more iterations,
  # extend the y-coordinates optimization path by its last entry
  # until it has the same length as the x-coordinate's optimization path
  F1.coordinate.y.path <- c(F1.coordinate.y.path, rep(tail(F1.coordinate.y.path, n=1), abs(path_difference)))
} else {
  # If the y-coordinate's optimization path had more iterations,
  # extend the x-coordinates optimization path by its last entry
  # until it has the same length as the y-coordinate's optimization path
  F1.coordinate.x.path <- c(F1.coordinate.x.path, rep(tail(F1.coordinate.x.path, n=1), abs(path_difference)))
}

# Initialize a new combined optimization path with the starting position
path <- vector("list", max_iterations*2)
path[[1]] <- c(F1.coordinate.x.path[1], F1.coordinate.y.path[1])

# Interleave the elements of both coordinate's optimization paths
# to form an optimization path in the original two-dimensional x-y plane.
i <- 2
j <- 2
while(i <= length(F1.coordinate.x.path)) {
  path[[j]] <- c(F1.coordinate.x.path[i], F1.coordinate.y.path[i-1])
  path[[j+1]] <- c(F1.coordinate.x.path[i], F1.coordinate.y.path[i])
  i <- i + 1
  j <- j + 2
}

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F1.coordinate.contour <- plot_ly(x=~F1.x, y=~F1.y, z=F1.z, width=800, height=500,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F1.minimum[1], y=F1.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F1.start[1], y=F1.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=30, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F1.minimum[1], y=F1.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="CD optimization of the six-hump camel function (F1)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F1.coordinate.contour, align="center")

In order to compare the performance of coordinate descent to gradient descent, we will have to also combine the performance metrics for all of the coordinates. For the total time taken for all coordinates to be optimized, we can simply sum the time taken for each one. For the number of iterations, we take the coordinate with the highest number of iterations:

# Adding together the time taken for each coordinate
F1.coordinate.time <- F1.coordinate.x.time + F1.coordinate.y.time
  
# Take the coordinate which had the maximum number of iterations
F1.coordinate.iterations <- max(as.numeric(c(F1.coordinate.x.results[[2]], F1.coordinate.y.results[[2]])))

Testing on the Peaks function

\(x\)-coordinate optimization

Optimizing the \(x\)-coordinate:

# Reset optimization path
reset_path()

# Run timed x-coordinate descent
F2.coordinate.x.time <- proc.time()
F2.coordinate.x.results <- coordinate.descent(F2.start[1], F2.start[2], 2, F2.d, 1, F2.minimum)
F2.coordinate.x.time <- proc.time() - F2.coordinate.x.time

# Trucate NULLs in optimization path list
F2.coordinate.x.path <- Filter(Negate(is.null), path)

Termination reason and number of iterations for \(x\)-coordinate optimization:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F2.coordinate.x.results[1], F2.coordinate.x.results[2]))
Termination reason: Converged
Number of iterations: 7

Benchmarks for \(x\)-coordinate optimization:

print(F2.coordinate.x.time)
   user  system elapsed 
  0.030   0.002   0.031
\(y\)-coordinate optimization

Optimizing the \(y\)-coordinate:

# Reset optimization path from x coordinate
reset_path()

# Run timed y-coordinate descent
F2.coordinate.y.time <- proc.time()
F2.coordinate.y.results <- coordinate.descent(F2.start[1], F2.start[2], 1, F2.d, 1, F2.minimum)
F2.coordinate.y.time <- proc.time() - F2.coordinate.y.time

# Trucate NULLs in optimization path list
F2.coordinate.y.path <- Filter(Negate(is.null), path)

Termination reason and number of iterations for \(y\)-coordinate optimization:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F2.coordinate.y.results[1], F2.coordinate.y.results[2]))
Termination reason: Converged
Number of iterations: 9

Benchmarks for \(y\)-coordinate optimization:

print(F2.coordinate.y.time)
   user  system elapsed 
  0.041   0.003   0.043
Solving the original optimization problem

Combining optimization paths:

# Calculate the difference between the number of iterations of both coordinate's optimization paths
path_difference <- length(F2.coordinate.x.path) - length(F2.coordinate.y.path)

# Accounting for difference in coordinates' number of iterations
if (path_difference > 0) {
  F2.coordinate.y.path <- c(F2.coordinate.y.path, rep(tail(F2.coordinate.y.path, n=1), abs(path_difference)))
} else {
  F2.coordinate.x.path <- c(F2.coordinate.x.path, rep(tail(F2.coordinate.x.path, n=1), abs(path_difference)))
}

# Initialize a new combined optimization path with the starting position
path <- vector("list", max_iterations*2)
path[[1]] <- c(F2.coordinate.x.path[1], F2.coordinate.y.path[1])

# Interleave the elements of both coordinate's optimization paths
# to form an optimization path in the original two-dimensional x-y plane.
i <- 2
j <- 2
while(i <= length(F2.coordinate.x.path)) {
  path[[j]] <- c(F2.coordinate.x.path[i], F2.coordinate.y.path[i-1])
  path[[j+1]] <- c(F2.coordinate.x.path[i], F2.coordinate.y.path[i])
  i <- i + 1
  j <- j + 2
}

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F2.coordinate.contour <- plot_ly(x=~F2.x, y=~F2.y, z=F2.z, width=700, height=600,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F2.minimum[1], y=F2.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F2.start[1], y=F2.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=30, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F2.minimum[1], y=F2.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="CD optimization of the peaks function (F2)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F2.coordinate.contour, align="center")

Combining the performance metrics for both coordinates:

# Adding together the time taken for each coordinate
F2.coordinate.time <- F2.coordinate.x.time + F2.coordinate.y.time
  
# Take the coordinate which had the maximum number of iterations
F2.coordinate.iterations <- max(as.numeric(c(F2.coordinate.x.results[[2]], F2.coordinate.y.results[[2]])))

Method comparison metrics

Benchmarks

Preparing the benchmark comparison plot:

# Dataframe representing the gradient and coordinate descent benchmarks on F1
F1.benchmarks.df <- data.frame(
  Method=rep(c("Gradient descent", "Coordinate descent"), each=3),
  Type=c("User", "System", "Elapsed (Total)"),
  Time=round(c(F1.gradient.time[1:3], F1.coordinate.time[1:3]), digits=3)
)

# Grouped bar plot for comparison of the benchmarks
F1.benchmarks.plot <- ggplot(data=F1.benchmarks.df, aes(x=Type, y=Time, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  geom_text(aes(label=Time), hjust=0.5, color="black", size=2.5, position = position_dodge(0.9), size=3.5) +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  theme_minimal() +
  ggtitle("F1 (six-hump camel function)") +
  theme(plot.margin=unit(c(0.5, 0, 0, 0), "cm")) +
  coord_flip()

# Dataframe representing the gradient and coordinate descent benchmarks on F2
F2.benchmarks.df <- data.frame(
  Method=rep(c("Gradient descent", "Coordinate descent"), each=3),
  Type=c("User", "System", "Elapsed (Total)"),
  Time=round(c(F2.gradient.time[1:3], F2.coordinate.time[1:3]), digits=3)
)

# Grouped bar plot for comparison of the benchmarks
F2.benchmarks.plot <- ggplot(data=F2.benchmarks.df, aes(x=Type, y=Time, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  geom_text(aes(label=Time), hjust=0.5, color="black", size=2.5, position = position_dodge(0.9), size=3.5) +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  theme_minimal() +
  ggtitle("F2 (peaks function)") +
  coord_flip()

# Arranging the subplots
benchmarks.plot <- ggarrange(F1.benchmarks.plot, F2.benchmarks.plot, nrow=2, common.legend=TRUE, legend="bottom")

Plotting the benchmarks comparison:

# Add a plot title
annotate_figure(benchmarks.plot, 
                top=text_grob("Gradient and coordinate descent benchmarks", size=16, face="bold"))

As explained earlier, coordinate descent tends to optimize faster (in terms of run-time) than gradient descent. Despite this, the experiment yielded mixed results, with coordinate descent optimizing \(F_1\) significantly slower than gradient descent. However, coordinate descent seems to perform better with \(F_2\), having a faster run-time than gradient descent in this case.

This variety in performance makes it difficult to conclude that one optimization method is better than the other, especially due to the fact that we did not perform repeated experiments or try other functions, or other combinations of \(\eta\), \(\epsilon\) and starting position.

More likely, certain implementation choices impacted the run-times of these optimization methods. Namely, both methods were implemented recursively, which may lead to issues such as having to deal with the recursive call stack frame. Additionally, the general implementation of the optimization methods were quite non-standard—especially for coordinate descent.

Number of iterations

Preparing the iteration comparison plot:

# Dataframe representing the gradient and coordinate descent iterations on F1
F1.iterations.df <- data.frame(
  Method=c("Gradient descent", "Coordinate descent"),
  Iterations=round(as.numeric(c(F1.gradient.results[[2]], F1.coordinate.iterations)))
)

# Bar plot for comparison of iterations
F1.iterations.plot <- ggplot(data=F1.iterations.df, aes(x=Method, y=Iterations, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  geom_text(aes(label=Iterations), hjust=3, color="white", size=4, position = position_dodge(0.9), size=3.5) +
  scale_y_continuous(breaks=function(x) unique(floor(pretty(seq(0, (max(x) + 1) * 1.1))))) + 
  theme_minimal() +
  theme(axis.text.y = element_blank(), axis.ticks.y = element_blank()) +
  ggtitle("F1 (six-hump camel function)") +
  theme(plot.margin=unit(c(0.5, 0, 0, 0), "cm")) +
  coord_flip()

# Dataframe representing the gradient and coordinate descent iterations on F2
F2.iterations.df <- data.frame(
  Method=c("Gradient descent", "Coordinate descent"),
  Iterations=round(as.numeric(c(F2.gradient.results[[2]], F2.coordinate.iterations)))
)

# Bar plot for comparison of iterations
F2.iterations.plot <- ggplot(data=F2.iterations.df, aes(x=Method, y=Iterations, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  geom_text(aes(label=Iterations), hjust=3, color="white", size=4, position = position_dodge(0.9), size=3.5) +
  scale_y_continuous(breaks=function(x) unique(floor(pretty(seq(0, (max(x) + 1) * 1.1))))) + 
  theme_minimal() +
  theme(axis.text.y = element_blank(), axis.ticks.y = element_blank()) +
  ggtitle("F2 (peaks function)") +
  coord_flip()

# Arranging the subplots
iterations.plot <- ggarrange(F1.iterations.plot, F2.iterations.plot, nrow=2, common.legend=TRUE, legend="bottom")

Plotting the iterations comparison:

# Add a plot title
annotate_figure(iterations.plot, 
                top=text_grob("Gradient and coordinate descent iterations", size=16, face="bold"))

Unlike benchmarks, the number of iterations that each of these optimization method takes to converge (if it does converge) does not vary per experiment—it will never change unless we change \(\eta\), \(\epsilon\) or the starting position, which we didn’t. For this reason, repeated experiments are not as necessary as they are for benchmarking, where the uncertainty of CPU resource allocation etc. is enough to warrant repeated experiments.

However, it still isn’t fair to make a concrete conclusion from these results, since we would need to test the optimization methods on different objective functions, different \(\eta\), \(\epsilon\) and starting positions.

Nevertheless, coordinate descent optimized the objective function \(F_1\) in two fewer iterations than gradient descent. However, for \(F_2\), both optimization methods took the same number of iterations (\(9\)) to optimize the function.

Resources

  1. https://en.wikipedia.org/wiki/Limited-memory_BFGS↩

  2. https://web.stanford.edu/~hastie/TALKS/glmnet.pdf↩

  3. https://en.wikipedia.org/wiki/Coordinate_descent↩

  4. https://www.sfu.ca/~ssurjano/camel6.html↩

  5. https://al-roomi.org/benchmarks/unconstrained/2-dimensions/63-peaks-function↩

  6. https://en.wikipedia.org/wiki/Derivative-free_optimization↩

  7. https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method↩

  8. https://ml-cheatsheet.readthedocs.io/en/latest/gradient_descent.html↩

  9. https://stat.ethz.ch/R-manual/R-devel/library/base/html/proc.time.html↩

LS0tCnRpdGxlOiBDb21wYXJpc29uIG9mIGdyYWRpZW50LWJhc2VkIGNvb3JkaW5hdGUgZGVzY2VudCBhbmQgZ3JhZGllbnQgZGVzY2VudCBvbiBjb250aW51b3VzIGJpdmFyaWF0ZSBmdW5jdGlvbnMKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBjb2RlX2ZvbGRpbmc6IG5vbmUKICAgIHRoZW1lOiBzcGFjZWxhYgogICAgdG9jOiB5ZXMKLS0tCgojIEludHJvZHVjdGlvbgoKV2l0aGluIHRoZSBzdWJqZWN0IGFyZWEgb2YgbWFjaGluZSBsZWFybmluZywgZ3JhZGllbnQgZGVzY2VudCBpcyBwZXJoYXBzIHRoZSBtb3N0IHdlbGwta25vd24gYW5kIGNvbW1vbmx5IHVzZWQgaXRlcmF0aXZlIG9wdGltaXphdGlvbiBtZXRob2QgZm9yIGZpbmRpbmcgdGhlIHBhcmFtZXRlcnMgdGhhdCBtaW5pbWl6ZSBlcnJvciBmdW5jdGlvbnMgc3VjaCBhcyByZXNpZHVhbCBzdW0gb2Ygc3F1YXJlcyBmb3IgKCRMXzEkLXJlZ3VsYXJpemVkKSBsaW5lYXIgcmVncmVzc2lvbiwgb3IgbmVnYXRpdmUgbG9nLWxpa2VsaWhvb2RzIGZvciBsb2dpc3RpYyByZWdyZXNzaW9uIGFuZCBuZXVyYWwgbmV0d29ya3MuCgpIb3dldmVyLCB0aGVyZSBhcmUgYSBmZXcgYWx0ZXJuYXRpdmUgbWV0aG9kcyB0aGF0IG1heSBwZXJmb3JtIGJldHRlciB0aGFuIGdyYWRpZW50IGRlc2NlbnQgaW4gc3BlY2lmaWMgY2FzZXMuIEZvciBleGFtcGxlOgoKLSAqKkxpbWl0ZWQtbWVtb3J5IEJGR1MgKEwtQkZHUykqKiBpcyBwYXJ0aWN1bGFybHkgc3VpdGVkIHRvIHByb2JsZW1zIHdpdGggdmVyeSBsYXJnZSBudW1iZXJzIG9mIHZhcmlhYmxlc1tebC1iZmdzXS4KLSAqKkNvb3JkaW5hdGUgZGVzY2VudCoqIGlzIGdlbmVyYWxseSBmYXN0ZXIgdGhhbiBncmFkaWVudCBkZXNjZW50LCBhbmQgaXMgX3N0YXRlLW9mLXRoZS1hcnRfIGZvciAkTF8xJC1yZWd1bGFyaXplZCByZWdyZXNzaW9uW15nbG1uZXRdLgoKLS0tCgpJbiB0aGlzIG5vdGVib29rLCB3ZSB3aWxsIGJlIGNvbXBhcmluZyBjb29yZGluYXRlIGFuZCBncmFkaWVudCBkZXNjZW50IGluIHRoZSBiaXZhcmlhdGUgZnVuY3Rpb24gc2V0dGluZy0tLWZ1bmN0aW9ucyBvbmx5IGFjY2VwdGluZyB0d28gaW5wdXRzLiBUaGlzIGNvbXBhcmlzb24gaXMgYWltZWQgYXQgdW5kZXJzdGFuZGluZyBvcHRpbWl6YXRpb24gbWV0aG9kcyBtb3JlIGFic3RyYWN0bHksIHJhdGhlciB0aGFuIHRoZWlyIGFwcGxpY2F0aW9ucyB0byBtYWNoaW5lIGxlYXJuaW5nLgoKSXQgaXMgaW1wb3J0YW50IHRvIG5vdGUgdGhhdCBjb29yZGluYXRlIGRlc2NlbnQgZ2VuZXJhbGx5IHJlZmVycyB0byB0aGUgYXBwcm9hY2ggb2YgbWluaW1pemluZyBhIG11bHRpdmFyaWF0ZSBmdW5jdGlvbiBieSBtaW5pbWl6aW5nIGl0IGluIG9uZSBkaXJlY3Rpb24gb3IgY29vcmRpbmF0ZSBhdCBhIHRpbWUgKHNvbHZpbmcgdW5pdmFyaWF0ZSBvcHRpbWl6YXRpb24gcHJvYmxlbXMgcmVwZWF0ZWRseSkuIFRoaXMgbWVhbnMgdGhhdCBpdCBpcyBwb3NzaWJsZSB0byBhcHBseSBjb29yZGluYXRlIGRlc2NlbnQgdG8gYm90aCBkaWZmZXJlbnRpYWJsZSBhbmQgZGVyaXZhdGl2ZS1mcmVlIGNvbnRleHRzW15jb29yZGluYXRlLWRlc2NlbnRdLgoKSG93ZXZlciwgaW4gdGhpcyBub3RlYm9vaywgY29vcmRpbmF0ZSBkZXNjZW50IHJlZmVycyB0byBncmFkaWVudC1iYXNlZCBjb29yZGluYXRlIGRlc2NlbnQuCgojIyBTZXR1cAoKYGBge3J9CiMgU2V0IHdvcmtpbmcgZGlyZWN0b3J5CnNldHdkKCJ+L0Rvd25sb2Fkcy9SL21pbmltaXplcnMiKQoKIyBJbnN0YWxsIGRlcGVuZGVuY2llcwojaW5zdGFsbC5wYWNrYWdlcygic2hpbnkiKQojaW5zdGFsbC5wYWNrYWdlcygicGxvdGx5IikKI2luc3RhbGwucGFja2FnZXMoInBseXIiKQojaW5zdGFsbC5wYWNrYWdlcygiZ2dwbG90MiIpCiNpbnN0YWxsLnBhY2thZ2VzKCJnZ3B1YnIiKQoKIyBSZXF1aXJlIGRlcGVuZGVuY2llcwpyZXF1aXJlKHNoaW55KQpyZXF1aXJlKHBsb3RseSkKcmVxdWlyZShwbHlyKQpyZXF1aXJlKGdncGxvdDIpCnJlcXVpcmUoZ2dwdWJyKQoKIyBTZXQgc2VlZCBmb3IgcmVwcm9kdWNpYmlsaXR5CnNldC5zZWVkKDkyOTIpCmBgYAoKIyMgVGVzdCBmdW5jdGlvbnMKCkNvbXBhcmlzb24gbWV0cmljcyB3aWxsIGluY2x1ZGUgYmVuY2htYXJrcywgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgYW5kIGNvbnZlcmdlbmNlL2RpdmVyZ2VuY2UuIFRoZXNlIG1ldHJpY3Mgd2lsbCBiZSB1c2VkIHRvIHRlc3QgYm90aCBvcHRpbWl6YXRpb24gbWV0aG9kcyBvbiB0d28gZGlmZmVyZW50aWFibGUgYml2YXJpYXRlIGZ1bmN0aW9uczogdGhlICoqU2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24qKiBhbmQgdGhlICoqUGVha3MgZnVuY3Rpb24qKi4KCiMjIyBTaXgtaHVtcCBjYW1lbCBmdW5jdGlvbgoKVGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uIGlzIGEgdGVzdCBmdW5jdGlvbiB1c2VkIGZvciBpbnZlc3RpZ2F0aW5nIHRoZSBwZXJmb3JtYW5jZSBvZiBvcHRpbWl6YXRpb24gYWxnb3JpdGhtcy5bXmNhbWVsXQoKVGhlIGZ1bmN0aW9uIGlzIGRlZmluZWQgYnk6CgokJApGXzEoeCx5KT1cbGVmdCg0LTIuMXheMitcZnJhY3t4XjR9ezN9XHJpZ2h0KXheMit4eSs0XGxlZnQoeV4yLTFccmlnaHQpeV4yCiQkCkRlc3BpdGUgYmVpbmcgd2VsbCBkZWZpbmVkIGZvciBhbGwgJCh4LHkpXGluXG1hdGhiYntSfV4yJCwgdGhlIGZvY2FsIHBvaW50IG9mIHRoaXMgZnVuY3Rpb24gaXMgd2l0aGluIHRoZSAkeCx5XGluWy02LDZdJCByZWdpb24sIHdoZXJlIGFsbCBvZiB0aGUgdHVybmluZyBwb2ludHMgb2YgdGhlIGZ1bmN0aW9uIGxpZS4gSG93ZXZlciwgZm9yIHZpc3VhbGl6YXRpb24sIHRoaXMgcmVnaW9uIGNhbiBiZSBtYWRlIHNtYWxsZXI6ICR4XGluWy0yLDJdLFwgeVxpblstMSwxXSQuCgpgYGB7cn0KIyBJbXBvcnQgU2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24Kc291cmNlKCJmdW5jdGlvbnMvY2FtZWwuUiIpCgojIFNldCBpbnB1dCB2YXJpYWJsZSByYW5nZXMKRjEueCA8LSBzZXEoLTIsIDIsIGxlbmd0aD0xMDApCkYxLnkgPC0gc2VxKC0xLCAxLCBsZW5ndGg9MTAwKQpGMS56IDwtIHQob3V0ZXIoRjEueCwgRjEueSwgRjEpKQoKIyBEaXNwbGF5IHBsb3QgYW5kIGNvbnRvdXJzCkYxLnBsb3QgPC0gcGxvdF9seSh4PUYxLngsIHk9RjEueSwgej1GMS56LCB3aWR0aD03MDAsIGhlaWdodD01MDApICU+JQogIGFkZF9zdXJmYWNlKGNvbnRvdXJzPWxpc3Qoej1saXN0KHNob3c9VFJVRSwgdXNlY29sb3JtYXA9VFJVRSwgaGlnaGxpZ2h0Y29sb3I9IiNmZjAwMDAiLCBwcm9qZWN0PWxpc3Qoej1UUlVFKSkpKSAlPiUKICBsYXlvdXQoc2NlbmU9bGlzdCh6YXhpcz1saXN0KHJhbmdlPWMoLTIsNikpLCBhc3BlY3Rtb2RlPSJtYW51YWwiLCBhc3BlY3RyYXRpbz1saXN0KHg9MSwgeT0xLCB6PTAuNikpLAogICAgICAgICB0aXRsZT0iU2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24gKEYxKSIpCgpkaXYoRjEucGxvdCwgYWxpZ249ImNlbnRlciIpCmBgYAoKIyMjIyBNaW5pbWEKCnwgVHlwZSB8ICR4JCB8ICR5JCB8ICRmKHgseSkkIHwKfC0tLS0tLXwtLS0tLXwtLS0tLXwtLS0tLS0tLS0tfAp8R2xvYmFsfCQwLjA4OTg0MiR8JC0wLjcxMjY1NiR8JC0xLjAzMTYyODQ1MyR8CnxHbG9iYWx8JC0wLjA4OTg0MiR8JDAuNzEyNjU2JHwkLTEuMDMxNjI4NDUzJHwKCiMjIyMgUGFydGlhbCBkZXJpdmF0aXZlcwoKVGhlIGdyYWRpZW50IHZlY3RvciAkXG5hYmxhIEZfMSh4LHkpJCBmb3IgdGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uIGNvbnNpc3RzIG9mIHRoZSBmb2xsb3dpbmcgcGFydGlhbCBkZXJpdmF0aXZlczoKCiQkClxiZWdpbnthbGlnbn0KICBcbmFibGEgRl8xKHgseSkKICAmPVxiZWdpbntwbWF0cml4fQogICAgXGZyYWN7XHBhcnRpYWwgRl8xfXtccGFydGlhbCB4fVxcCiAgICBcZnJhY3tccGFydGlhbCBGXzF9e1xwYXJ0aWFsIHl9CiAgXGVuZHtwbWF0cml4fVxcCiAgJj1cYmVnaW57cG1hdHJpeH0KICAgIDJcbGVmdCh4XjUtNC4yeF4zKzR4KzAuNXlccmlnaHQpCiAgICBcXAogICAgeCsxNnleMy04eQogIFxlbmR7cG1hdHJpeH0KXGVuZHthbGlnbn0KJCQKCiMjIyBUaGUgUGVha3MgZnVuY3Rpb24KClRoZSBQZWFrcyBmdW5jdGlvbltecGVha3NdIGlzIGEgZnVuY3Rpb24gb2Z0ZW4gdXNlZCB0byBkZW1vbnN0cmF0ZSAzRCBncmFwaGluZyBzb2Z0d2FyZSBvciBsaWJyYXJpZXMgaW4gTUFUTEFCIGFuZCBvdGhlciBwcm9ncmFtbWluZyBsYW5ndWFnZXMuCgpUaGUgZnVuY3Rpb24gaXMgZGVmaW5lZCBieToKCiQkClxiZWdpbnthbGlnbn0KICBGXzIoeCx5KSY9CiAgMygxLXgpXjJlXnsteF4yLSh5KzEpXjJ9XFwKICAmKzEwXGxlZnQoXGZyYWN7MX17NX14LXheMy15XjVccmlnaHQpZV57LVxsZWZ0KHheMit5XjJccmlnaHQpfVxcCiAgJitcZnJhY3sxfXszfWVeey0oeCsxKV4yLXleMn0KXGVuZHthbGlnbn0KJCQKCkZvciBvcHRpbWl6YXRpb24gdGVzdHMsIHRoaXMgZnVuY3Rpb24gaXMgbm9ybWFsbHkgcmVzdHJpY3RlZCB0byB0aGUgJHgseVxpblstNCw0XSQgcmVnaW9uLCBhcyB0aGlzIGlzIHdoZXJlIHRoZSBleHRyZW1hIG9mIHRoZSBmdW5jdGlvbiBsaWUuIEhvd2V2ZXIsIGZvciB2aXN1YWxpemF0aW9uIHB1cnBvc2VzLCAkWy0zLDNdJCBpcyBwcmVmZXJhYmxlIGZvciAkeCQuCgpgYGB7cn0KIyBJbXBvcnQgUGVha3MgZnVuY3Rpb24Kc291cmNlKCJmdW5jdGlvbnMvcGVha3MuUiIpCgojIFNldCBpbnB1dCB2YXJpYWJsZSByYW5nZXMKRjIueCA8LSBzZXEoLTMsIDMsIGxlbmd0aD0xMDApCkYyLnkgPC0gc2VxKC0zLCAzLCBsZW5ndGg9MTAwKQpGMi56IDwtIHQob3V0ZXIoRjIueCwgRjIueSwgRjIpKQoKIyBEaXNwbGF5IHBsb3QgYW5kIGNvbnRvdXJzCkYyLnBsb3QgPC0gcGxvdF9seSh4PUYyLngsIHk9RjIueSwgej1GMi56LCB3aWR0aD03MDAsIGhlaWdodD01MDApICU+JQogIGFkZF9zdXJmYWNlKGNvbnRvdXJzPWxpc3Qoej1saXN0KHNob3c9VFJVRSwgdXNlY29sb3JtYXA9VFJVRSwgaGlnaGxpZ2h0Y29sb3I9IiNmZjAwMDAiLCBwcm9qZWN0PWxpc3Qoej1UUlVFKSkpKSAlPiUKICBsYXlvdXQoc2NlbmU9bGlzdChhc3BlY3Rtb2RlPSJtYW51YWwiLCBhc3BlY3RyYXRpbz1saXN0KHg9MSwgeT0xLCB6PTAuNjUpKSwKICAgICAgICAgdGl0bGU9IlBlYWtzIGZ1bmN0aW9uIChGMikiKQoKZGl2KEYyLnBsb3QsIGFsaWduPSJjZW50ZXIiKQpgYGAKCiMjIyMgTWluaW1hCgp8IFR5cGUgfCAkeCQgfCAkeSQgfCAkZih4LHkpJCB8CnwtLS0tLS18LS0tLS18LS0tLS18LS0tLS0tLS0tLXwKfEdsb2JhbHwkMC4yMjgyNzk5OTk5JHwkLTEuNjI1NTMxMDcyMCR8JC02LjU1MTEzMzMzMjYkfAoKIyMjIyBQYXJ0aWFsIGRlcml2YXRpdmVzCgpUaGUgZ3JhZGllbnQgdmVjdG9yICRcbmFibGEgRl8yKHgseSkkIGZvciB0aGUgUGVha3MgZnVuY3Rpb24gY29uc2lzdHMgb2YgdGhlIGZvbGxvd2luZyBwYXJ0aWFsIGRlcml2YXRpdmVzOgoKJCQKXGJlZ2lue2FsaWdufQogIFxuYWJsYSBGXzIoeCx5KQogICY9XGJlZ2lue3BtYXRyaXh9CiAgICBcZnJhY3tccGFydGlhbCBGXzJ9e1xwYXJ0aWFsIHh9XFwKICAgIFxmcmFje1xwYXJ0aWFsIEZfMn17XHBhcnRpYWwgeX0KICBcZW5ke3BtYXRyaXh9XFwKICAmPVxiZWdpbntwbWF0cml4fQogICAgLVxmcmFjezJ9ezN9ZV57LVxiaWcoeF4yICsgMiB4ICsgKHkgKyAxKV4yXGJpZyl9CiAgICBcQmlnKAogICAgICBlXnsyeCsyeSsxfVxiaWcoCiAgICAgICAgMzB4XjMtNnheMiszMHgoeV41LTEpKzMKICAgICAgXGJpZykKICAgICAgKwogICAgICA5ZV57Mnh9XGxlZnQoCiAgICAgICB4XjMtMnheMisxCiAgICAgIFxyaWdodCkKICAgICAgKwogICAgICAoeCsxKVxsZWZ0KC1lXnsyeX1ccmlnaHQpCiAgICBcQmlnKVxcCiAgICAtXGZyYWN7Mn17M31lXnstXGJpZyh4XjIrMngrKHkrMSleMlxiaWcpfQogICAgXEJpZygKICAgICAgM3llXnsyeCsyeSsxfVxiaWcoCiAgICAgICAgMTB4XjItMngrNSgyeV4yLTUpeV4zCiAgICAgIFxiaWcpCiAgICAgICsKICAgICAgOWVeezJ4fSgxLXgpXjIoeSsxKQogICAgICAtCiAgICAgIHllXnsyeX0KICAgIFxCaWcpCiAgXGVuZHtwbWF0cml4fQpcZW5ke2FsaWdufQokJAoKVGhlc2UgcGFydGlhbCBkZXJpdmF0aXZlcyBhcmUgZmFyIG1vcmUgY29tcGxleCB0aGFuIHRob3NlIG9mIHRoZSBTaXgtaHVtcCBjYW1lbCBmdW5jdGlvbi4gU2luY2UgYm90aCBvZiB0aGUgb3B0aW1pemF0aW9uIG1ldGhvZHMgd2UgYXJlIHRlc3RpbmcgYXJlIGdyYWRpZW50LWJhc2VkLCBpdCBpcyBsaWtlbHkgdGhhdCBiZW5jaG1hcmtzIGZvciB0aGlzIHRlc3QgZnVuY3Rpb24gd2lsbCB0YWtlIHNpZ25pZmljYW50bHkgbG9uZ2VyLgoKV2l0aCBjb21wbGV4IGRlcml2YXRpdmVzIHN1Y2ggYXMgdGhlc2UgKG9yIHdoZW4gdGhlIGZ1bmN0aW9uIGlzIG5vbi1kaWZmZXJlbnRpYWJsZSBlbnRpcmVseSksIGl0IGlzIG9mdGVuIG1vcmUgcHJlZmVyYWJsZSB0byB1c2UgZGVyaXZhdGl2ZS1mcmVlIG9wdGltaXphdGlvbiBtZXRob2RzW15kZXJpdmF0aXZlLWZyZWVdIHN1Y2ggYXMgdGhlIE5lbGRlci1NZWFkIG1ldGhvZFtebmVsZGVyLW1lYWRdLgoKIyMgT3B0aW1pemF0aW9uIG1ldGhvZHMKCiMjIyBHcmFkaWVudCBkZXNjZW50CgpHcmFkaWVudCBkZXNjZW50IGlzIGEgZ3JhZGllbnQtYmFzZWQgaXRlcmF0aXZlIG9wdGltaXphdGlvbiBtZXRob2QuIEdyYWRpZW50IGRlc2NlbnQgd29ya3MgYnkgaXRlcmF0aXZlbHkgdXBkYXRpbmcgdGhlIGN1cnJlbnQgcG9zaXRpb24gYnkgdGFraW5nIGEgc21hbGwgc3RlcCBpbiB0aGUgZGlyZWN0aW9uIG9mIHN0ZWVwZXN0IGRlc2NlbnRbXmdyYWRpZW50LWRlc2NlbnRdLgoKJCQKXG1hdGhiZnt4fV97aSsxfSBcbGVmdGFycm93IFxtYXRoYmZ7eH1faSAtIFxldGEgXG5hYmxhIEYoXG1hdGhiZnt4fSkKJCQKCj4gKipXaGVyZSoqOgo+Cj4gLSAkXGV0YSQgaXMgdGhlIGxlYXJuaW5nIHJhdGUgZm9yIHRoZSBhbGdvcml0aG0tLS10aGUgc2l6ZSBvZiB0aGUgc3RlcCB0YWtlbiBvbiBlYWNoIGl0ZXJhdGlvbi4KPiAtICRcbmFibGEgRihcbWF0aGJme3h9KSQgaXMgdGhlIGdyYWRpZW50IHZlY3RvciBvZiAkRihcbWF0aGJme3h9KSQsIHdoaWNoIHJlcHJlc2VudHMgdGhlIGRpcmVjdGlvbiBvZiBzdGVlcGVzdCAqKmFzY2VudCoqLgoKV2l0aCBhIGJpdmFyaWF0ZSBmdW5jdGlvbiAkRih4LHkpJCwgd2UgY2FuIHVwZGF0ZSB0aGUgdmVjdG9yICRcYmVnaW57cG1hdHJpeH14IFxcIHlcZW5ke3BtYXRyaXh9JCB3aXRoOgoKJCQKXGJlZ2lue3BtYXRyaXh9CiAgeCBcXCB5ClxlbmR7cG1hdHJpeH0KXGxlZnRhcnJvdwpcYmVnaW57cG1hdHJpeH0KICB4IFxcIHkKXGVuZHtwbWF0cml4fQotXGV0YVxiZWdpbntwbWF0cml4fQogIFxmcmFje1xwYXJ0aWFsIEZ9e1xwYXJ0aWFsIHh9IFxcCiAgXGZyYWN7XHBhcnRpYWwgRn17XHBhcnRpYWwgeX0KXGVuZHtwbWF0cml4fQokJApDaG9vc2luZyB0aGUgbGVhcm5pbmcgcmF0ZSAkXGV0YSQgaXMgYSBmcmVxdWVudCBwcm9ibGVtIGluIG9wdGltaXphdGlvbi0tLXRvbyBsYXJnZSBvZiBhIGxlYXJuaW5nIHJhdGUgc29tZXRpbWVzIGxlYWRzIHRvIGRpdmVyZ2VuY2UgYW5kIG1pc3NpbmcgdGhlIG1pbmltdW0gZHVlIHRvIGhhdmluZyBzdWNoIGxhcmdlIHN0ZXBzLiBDb252ZXJzZWx5LCBhIHZlcnkgc21hbGwgbGVhcm5pbmcgcmF0ZSB3aWxsIHJlcXVpcmUgbWFueSBpdGVyYXRpb25zIHRvIGNvbnZlcmdlLCB3aGljaCBjYW4gYmUgY29zdGx5IGluIHRlcm1zIG9mIHRpbWUgYW5kIENQVS9tZW1vcnkgdXNhZ2UuCgpJbiBvcmRlciB0byBlbnN1cmUgY29udmVyZ2VuY2UsIHdlIHdpbGwgdXNlIGEgc21hbGwgbGVhcm5pbmcgcmF0ZS4KYGBge3J9CiMgU2V0IGEgc21hbGwgbGVhcm5pbmcgcmF0ZQpyYXRlIDwtIDAuMDQ3NQpgYGAKCkl0IGlzIGFsc28gbmVjZXNzYXJ5IHRvIHNldCBhIG1heGltdW0gbnVtYmVyIG9mIGl0ZXJhdGlvbnMgZm9yIGl0ZXJhdGl2ZSBtZXRob2RzLiBJbiB0aGUgZXZlbnQgdGhhdCB0aGUgbWV0aG9kIGRpdmVyZ2VzLCBpdCB3aWxsIHN0aWxsIHRlcm1pbmF0ZSBleGVjdXRpb24uIExpa2V3aXNlLCBpZiAkXGV0YSQgaXMgdG9vIHNtYWxsIGFuZCB0b28gbWFueSBpdGVyYXRpb25zIGhhdmUgcGFzc2VkIHdpdGhvdXQgcmVhY2hpbmcgYSBtaW5pbXVtLCB0aGUgbWV0aG9kIHdpbGwgc3RvcC4KCkluIHRoaXMgY2FzZSwgdGhlIG1heGltdW0gbnVtYmVyIG9mIGl0ZXJhdGlvbnMgd2lsbCBiZSAkMjAwJC4KYGBge3J9CiMgU2V0IG1heGltdW0gbnVtYmVyIG9mIGl0ZXJhdGlvbnMKbWF4X2l0ZXJhdGlvbnMgPC0gMjAwCmBgYAoKSW4gdGhpcyBub3RlYm9vaywgd2Ugd2lsbCBzYXkgdGhhdCBhbiBvcHRpbWl6YXRpb24gbWV0aG9kIGNvbnZlcmdlcyB0byBhIG1pbmltdW0gcG9pbnQgJFxiZWdpbntwbWF0cml4fXheKiBcXCB5XipcZW5ke3BtYXRyaXh9JCBpZiBpdCByZWFjaGVzIGEgcG9pbnQgJFxiZWdpbntwbWF0cml4fXggXFwgeVxlbmR7cG1hdHJpeH0kIHN1Y2ggdGhhdCB0aGUgRXVjbGlkZWFuIGRpc3RhbmNlICgkTF8yJCBub3JtKSBiZXR3ZWVuIHRoZSB0d28gaXMgbGVzcyB0aGFuIHNvbWUgJFxlcHNpbG9uXGluXG1hdGhiYntSXit9JC4gSW4gb3RoZXIgd29yZHMsIGlmICRcYmVnaW57cG1hdHJpeH14IFxcIHlcZW5ke3BtYXRyaXh9JCBpcyBpbiB0aGUgJFxlcHNpbG9uJC1uZWlnaGJvdXJob29kIG9mICRcYmVnaW57cG1hdHJpeH14XiogXFwgeV4qXGVuZHtwbWF0cml4fSQ6CiQkClxsZWZ0fFxsZWZ0fAogIFxiZWdpbntwbWF0cml4fXheKiBcXCB5XipcZW5ke3BtYXRyaXh9CiAgLQogIFxiZWdpbntwbWF0cml4fXggXFwgeVxlbmR7cG1hdHJpeH0KXHJpZ2h0fFxyaWdodHxfMiA8IFxlcHNpbG9uXFwKJCQKYGBge3J9CiMgU2V0IGEgc21hbGwgZXBzaWxvbgplcHNpbG9uIDwtIDAuMDUKYGBgCgpXZSBkZWZpbmUgdGhlIGdyYWRpZW50IGRlc2NlbnQgYWxnb3JpdGhtIHJlY3Vyc2l2ZWx5IGFzOgpgYGB7cn0KIyBHcmFkaWVudCBkZXNjZW50IChyZWN1cnNpdmUgaW1wbGVtZW50YXRpb24pCiMKIyBQYXJhbWV0ZXJzOgojICAgeDogVGhlIHgtY29vcmRpbmF0ZSBhdCB0aGUgY3VycmVudCBwb3NpdGlvbgojICAgeTogVGhlIHktY29vcmRpbmF0ZSBhdCB0aGUgY3VycmVudCBwb3NpdGlvbgojICAgRlVOOiBUaGUgZ3JhZGllbnQgdmVjdG9yIGZvciB0aGUgZnVuY3Rpb24gYmVpbmcgb3B0aW1pemVkCiMgICBpdGVyYXRpb25zOiBUaGUgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgKHNob3VsZCBzdGFydCBhdCAxKQojICAgbWluaW11bTogVGhlIGFjdHVhbCBtaW5pbXVtIG9mIHRoZSBmdW5jdGlvbgojCiMgUmV0dXJuczoKIyAgIEEgdHVwbGUgY29uc2lzdGluZyBvZiAodGVybWluYXRpb24gcmVhc29uLCBpdGVyYXRpb25zKS4KIwpncmFkaWVudC5kZXNjZW50IDwtIGZ1bmN0aW9uKHgsIHksIEZVTiwgaXRlcmF0aW9ucywgbWluaW11bSkgewogICMgQ2hlY2sgZm9yIG1heGltdW0gaXRlcmF0aW9ucwogIGlmKGl0ZXJhdGlvbnMgPiBtYXhfaXRlcmF0aW9ucykgcmV0dXJuKGMoIk1heGltdW0gaXRlcmF0aW9ucyByZWFjaGVkIiwgaXRlcmF0aW9ucy0xKSkKICAjIENoZWNrIGZvciBjb252ZXJnZW5jZQogIGlmKGRpc3QocmJpbmQoYyh4LCB5KSwgbWluaW11bSkpIDw9IGVwc2lsb24pIHJldHVybihjKCJDb252ZXJnZWQiLCBpdGVyYXRpb25zLTEpKQoKICAjIEFkZCBzdGFydGluZyBwb2ludCB0byBwYXRoIGlmIGl0IGlzIHRoZSBmaXJzdCBpdGVyYXRpb24KICBpZihpdGVyYXRpb25zID09IDEpIHBhdGhbWzFdXSA8PC0gYyh4LCB5KQoKICAjIE1ha2UgYW4gdXBkYXRlIHRvIHRoZSBjdXJyZW50IHBvc2l0aW9uCiAgdXBkYXRlZCA8LSBjKHgsIHkpIC0gcmF0ZSAqIEZVTih4LCB5KQoKICAjIEluY3JlbWVudCBpdGVyYXRpb25zIGFuZCBzdG9yZSB1cGRhdGVkIHBvc2l0aW9uIGluIGBwYXRoYCB2YXJpYWJsZQogIGl0ZXJhdGlvbnMgPC0gaXRlcmF0aW9ucyArIDEKICBwYXRoW1tpdGVyYXRpb25zXV0gPDwtIHVwZGF0ZWQKCiAgIyBNYWtlIHVwZGF0ZXMgcmVjdXJzaXZlbHkKICBncmFkaWVudC5kZXNjZW50KHVwZGF0ZWRbMV0sIHVwZGF0ZWRbMl0sIEZVTiwgaXRlcmF0aW9ucywgbWluaW11bSkKfQpgYGAKCj4gKipXaGVyZSoqOiBgcGF0aGAgaXMgYSBnbG9iYWwgdmFyaWFibGUgdGhhdCBzdG9yZXMgYWxsIG9mIHRoZSBpbnRlcm1lZGlhdGUgdmVjdG9ycyBkdXJpbmcgdGhlIG9wdGltaXphdGlvbiBwcm9jZXNzLgoKIyMjIyBUZXN0aW5nIG9uIHRoZSBTaXgtaHVtcCBjYW1lbCBmdW5jdGlvbgoKQmVmb3JlIHdlIHN0YXJ0IHRlc3RpbmcsIHdlIG5lZWQgYSBtaW5pbXVtIG9mIGludGVyZXN0LCBhbG9uZyB3aXRoIGEgc3RhcnRpbmcgcG9pbnQgZm9yIHRoZSBvcHRpbWl6YXRpb24gcHJvY2VzczoKYGBge3J9CiMgTWluaW11bSBvZiBpbnRlcmVzdApGMS5taW5pbXVtIDwtIGMoMC4wODk4NDIsIC0wLjcxMjY1NikKCiMgU3RhcnRpbmcgcG9pbnQKRjEuc3RhcnQgPC0gYygwLjg1LCAwKQpgYGAKCkFkZGl0aW9uYWxseSwgd2Ugd2lsbCBuZWVkIHRvIGluaXRpYWxpemUgdGhlIGBwYXRoYCB2YXJpYWJsZSBmb3Iga2VlcGluZyB0cmFjayBvZiB0aGUgdXBkYXRlZCB2ZWN0b3JzIGR1cmluZyB0aGUgb3B0aW1pemF0aW9uIHByb2Nlc3MuIFRoaXMgdmFyaWFibGUgd2lsbCBiZSByZXVzZWQgZm9yIG90aGVyIHRlc3RzLCBzbyB3ZSB3aWxsIGFsc28gZGVmaW5lIGEgcmVzZXQgZnVuY3Rpb24uCmBgYHtyfQojIENyZWF0ZSBhbiBlbXB0eSBwYXRoIHZlY3RvcgpwYXRoIDwtIHZlY3RvcigibGlzdCIsIG1heF9pdGVyYXRpb25zKQoKIyBSZXNldCBmdW5jdGlvbiBmb3IgdGhlIGBwYXRoYCB2YXJpYWJsZQpyZXNldF9wYXRoIDwtIGZ1bmN0aW9uKCkgeyBwYXRoIDw8LSB2ZWN0b3IoImxpc3QiLCBtYXhfaXRlcmF0aW9ucykgfQpgYGAKClJ1bm5pbmcgdGhlIGdyYWRpZW50IGRlc2NlbnQgbWV0aG9kICh3aXRoIGJlbmNobWFya2luZyk6CmBgYHtyfQojIFJ1biB0aW1lZCBncmFkaWVudCBkZXNjZW50CkYxLmdyYWRpZW50LnRpbWUgPC0gcHJvYy50aW1lKCkKRjEuZ3JhZGllbnQucmVzdWx0cyA8LSBncmFkaWVudC5kZXNjZW50KEYxLnN0YXJ0WzFdLCBGMS5zdGFydFsyXSwgRjEuZCwgMSwgRjEubWluaW11bSkKRjEuZ3JhZGllbnQudGltZSA8LSBwcm9jLnRpbWUoKSAtIEYxLmdyYWRpZW50LnRpbWUKYGBgCgpQbG90dGluZyB0aGUgY29udG91ciBhbmQgcGF0aCBvZiB1cGRhdGVzOgpgYGB7ciwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KIyBDb252ZXJ0IHRoZSBgcGF0aGAgdmFyaWFibGUgdG8gYSBtYXRyaXgKcGF0aCA8LSBtYXRyaXgodW5saXN0KHBhdGgpLCBuY29sPTIsIGJ5cm93PVRSVUUpCgojIERpc3BsYXkgY29udG91ciBhbmQgb3B0aW1pemF0aW9uIHBhdGgKRjEuZ3JhZGllbnQuY29udG91ciA8LSBwbG90X2x5KHg9fkYxLngsIHk9fkYxLnksIHo9RjEueiwgd2lkdGg9ODAwLCBoZWlnaHQ9NTAwLAogICAgICAgICAgICAgICAgICAgICAgdHlwZT0iY29udG91ciIsIGNvbnRvdXJzPWxpc3Qoc2hvd2xhYmVscyA9IFRSVUUpKSAlPiUKCiAgIyBBZGQgb3B0aW1pemF0aW9uIHBhdGggdHJhY2UKICBhZGRfdHJhY2UoeD1wYXRoWywxXSwgeT1wYXRoWywyXSwgdHlwZT0ic2NhdHRlciIsIG5hbWU9Ik9wdGltaXphdGlvbiBwYXRoIiwgbW9kZT0ibGluZSIpICU+JQoKICAjIEFkZCBjcm9zcyBhdCB0YXJnZXQgbWluaW11bSBwb3NpdGlvbgogIGFkZF90cmFjZSh4PUYxLm1pbmltdW1bMV0sIHk9RjEubWluaW11bVsyXSwgdHlwZT0ic2NhdHRlciIsIG5hbWU9IlRhcmdldCBtaW5pbXVtIiwKICAgICAgICAgICAgbW9kZT0ibWFya2VycyIsIG1hcmtlcj1saXN0KGNvbG9yPSIjNWVjNGE3Iiwgc2l6ZT02LCBzeW1ib2w9IngiKSkgJT4lCgogICMgQWRkIGFycm93IGFuZCBhbm5vdGF0aW9uIGZvciBzdGFydGluZyBwb3NpdGlvbgogIGFkZF9hbm5vdGF0aW9ucyh4PUYxLnN0YXJ0WzFdLCB5PUYxLnN0YXJ0WzJdLCB0ZXh0PSJTdGFydCIsCiAgICAgICAgICAgICAgICAgIHNob3dhcnJvdz1UUlVFLCBhcnJvd2hlYWQ9NCwgYXJyb3dzaXplPS41LCBhcnJvd2NvbG9yPSd3aGl0ZScsIGF4PTMwLCBheT0tMzAsCiAgICAgICAgICAgICAgICAgIGZvbnQ9bGlzdChjb2xvciA9ICcjODFjY2MyJywgZmFtaWx5PSdoZWx2ZXRpY2EnLCBzaXplID0gMTQpKSAlPiUKCiAgIyBBZGQgYXJyb3cgYW5kIGFubm90YXRpb24gZm9yIHRhcmdldCBtaW5pbXVtCiAgYWRkX2Fubm90YXRpb25zKHg9RjEubWluaW11bVsxXSwgeT1GMS5taW5pbXVtWzJdLCB0ZXh0PSJUYXJnZXRcbm1pbmltdW0iLAogICAgICAgICAgICAgICAgICBzaG93YXJyb3c9VFJVRSwgYXJyb3doZWFkPTQsIGFycm93c2l6ZT0uNSwgYXJyb3djb2xvcj0nd2hpdGUnLCBheD0tODAsIGF5PS0zMCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZGluZyBhbmQgcG9zaXRpb25pbmcgcGxvdCB0aXRsZQogIGxheW91dCh0aXRsZT0iR0Qgb3B0aW1pemF0aW9uIG9mIHRoZSBzaXgtaHVtcCBjYW1lbCBmdW5jdGlvbiAoRjEpIiwgbWFyZ2luPWxpc3QobD0xMjUsIHI9MCwgdD02MCwgYj02MCkpCgojIERpc3BsYXkgdGhlIGNvbnRvdXIgcGxvdApkaXYoRjEuZ3JhZGllbnQuY29udG91ciwgYWxpZ249ImNlbnRlciIpCmBgYAoKVGVybWluYXRpb24gcmVhc29uIGFuZCBudW1iZXIgb2YgaXRlcmF0aW9uczoKYGBge3J9CmNhdChzcHJpbnRmKCJUZXJtaW5hdGlvbiByZWFzb246ICVzXG5OdW1iZXIgb2YgaXRlcmF0aW9uczogJXMiLCBGMS5ncmFkaWVudC5yZXN1bHRzWzFdLCBGMS5ncmFkaWVudC5yZXN1bHRzWzJdKSkKYGBgCgpCZW5jaG1hcmtpbmcgZm9yIHRoZXNlIG9wdGltaXphdGlvbiBtZXRob2RzIHdpbGwgYmUgZG9uZSB3aXRoIHRoZSBgcHJvYy50aW1lYCBiYXNlIGZ1bmN0aW9uIGluIFJbXnByb2MtdGltZV0uIFRoaXMgZnVuY3Rpb24gcmVjb3JkcyB0aGUgdGltZSB0YWtlbiBmb3IgYSBzcGVjaWZpYyBhY3Rpb24gdG8gZmluaXNoIGV4ZWN1dGlvbiwgYWNjb3JkaW5nIHRocmVlIGRpZmZlcmVudCB0aW1lIG1lYXN1cmVzOgoKMS4gYHVzZXJgOiBUaGUgQ1BVIHRpbWUgY2hhcmdlZCBmb3IgdGhlIGV4ZWN1dGlvbiBvZiB1c2VyIGluc3RydWN0aW9ucyBvZiB0aGUgY2FsbGluZyBwcm9jZXNzLgoyLiBgc3lzdGVtYDogVGhlIENQVSB0aW1lIGNoYXJnZWQgZm9yIGV4ZWN1dGlvbiBieSB0aGUgc3lzdGVtIG9uIGJlaGFsZiBvZiB0aGUgY2FsbGluZyBwcm9jZXNzLgozLiBgZWxhcHNlZGA6IFRoZSAicmVhbCIgZWxhcHNlZCB0aW1lIHNpbmNlIHRoZSBwcm9jZXNzIHdhcyBzdGFydGVkLgoKUHJpbnRpbmcgdGhlIGBwcm9jX3RpbWVgIHJlc3VsdCBkaXNwbGF5cyB0aGVzZSBtZWFzdXJlcyBpbiBvcmRlcjoKYGBge3J9CnByaW50KEYxLmdyYWRpZW50LnRpbWUpCmBgYAoKIyMjIyBUZXN0aW5nIG9uIHRoZSBQZWFrcyBmdW5jdGlvbgoKU2V0dGluZyBhIG1pbmltdW0gb2YgaW50ZXJlc3QsIGFsb25nIHdpdGggYSBzdGFydGluZyBwb2ludDoKYGBge3J9CiMgTWluaW11bSBvZiBpbnRlcmVzdApGMi5taW5pbXVtIDwtIGMoMC4yMjgyNzk5OTk5NzkyMzcsIC0xLjYyNTUzMTA3MTk1NDQ2NCkKCiMgU3RhcnRpbmcgcG9pbnQKRjIuc3RhcnQgPC0gYygxLCAtMC4yKQpgYGAKClJlc2V0dGluZyB0aGUgb3B0aW1pemF0aW9uIHBhdGggdmFyaWFibGUgKGBwYXRoYCkgYW5kIHJ1bm5pbmcgdGhlIGdyYWRpZW50IGRlc2NlbnQgbWV0aG9kICh3aXRoIGJlbmNobWFya2luZyk6CmBgYHtyfQojIFJlc2V0dGluZyBvcHRpbWl6YXRpb24gcGF0aApyZXNldF9wYXRoKCkKCiMgUnVuIHRpbWVkIGdyYWRpZW50IGRlc2NlbnQKRjIuZ3JhZGllbnQudGltZSA8LSBwcm9jLnRpbWUoKQpGMi5ncmFkaWVudC5yZXN1bHRzIDwtIGdyYWRpZW50LmRlc2NlbnQoRjIuc3RhcnRbMV0sIEYyLnN0YXJ0WzJdLCBGMi5kLCAxLCBGMi5taW5pbXVtKQpGMi5ncmFkaWVudC50aW1lIDwtIHByb2MudGltZSgpIC0gRjIuZ3JhZGllbnQudGltZQpgYGAKClBsb3R0aW5nIHRoZSBjb250b3VyIGFuZCBwYXRoIG9mIHVwZGF0ZXM6CmBgYHtyLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIENvbnZlcnQgdGhlIGBwYXRoYCB2YXJpYWJsZSB0byBhIG1hdHJpeApwYXRoIDwtIG1hdHJpeCh1bmxpc3QocGF0aCksIG5jb2w9MiwgYnlyb3c9VFJVRSkKCiMgRGlzcGxheSBjb250b3VyIGFuZCBvcHRpbWl6YXRpb24gcGF0aApGMi5ncmFkaWVudC5jb250b3VyIDwtIHBsb3RfbHkoeD1+RjIueCwgeT1+RjIueSwgej1GMi56LCB3aWR0aD03MDAsIGhlaWdodD02MDAsCiAgICAgICAgICAgICAgICAgICAgICB0eXBlPSJjb250b3VyIiwgY29udG91cnM9bGlzdChzaG93bGFiZWxzID0gVFJVRSkpICU+JQoKICAjIEFkZCBvcHRpbWl6YXRpb24gcGF0aCB0cmFjZQogIGFkZF90cmFjZSh4PXBhdGhbLDFdLCB5PXBhdGhbLDJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iT3B0aW1pemF0aW9uIHBhdGgiLCBtb2RlPSJsaW5lIikgJT4lCgogICMgQWRkIGNyb3NzIGF0IHRhcmdldCBtaW5pbXVtIHBvc2l0aW9uCiAgYWRkX3RyYWNlKHg9RjIubWluaW11bVsxXSwgeT1GMi5taW5pbXVtWzJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iVGFyZ2V0IG1pbmltdW0iLAogICAgICAgICAgICBtb2RlPSJtYXJrZXJzIiwgbWFya2VyPWxpc3QoY29sb3I9IiM1ZWM0YTciLCBzaXplPTYsIHN5bWJvbD0ieCIpKSAlPiUKCiAgIyBBZGQgYXJyb3cgYW5kIGFubm90YXRpb24gZm9yIHN0YXJ0aW5nIHBvc2l0aW9uCiAgYWRkX2Fubm90YXRpb25zKHg9RjIuc3RhcnRbMV0sIHk9RjIuc3RhcnRbMl0sIHRleHQ9IlN0YXJ0IiwKICAgICAgICAgICAgICAgICAgc2hvd2Fycm93PVRSVUUsIGFycm93aGVhZD00LCBhcnJvd3NpemU9LjUsIGFycm93Y29sb3I9J3doaXRlJywgYXg9LTUsIGF5PS00MCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZCBhcnJvdyBhbmQgYW5ub3RhdGlvbiBmb3IgdGFyZ2V0IG1pbmltdW0KICBhZGRfYW5ub3RhdGlvbnMoeD1GMi5taW5pbXVtWzFdLCB5PUYyLm1pbmltdW1bMl0sIHRleHQ9IlRhcmdldFxubWluaW11bSIsCiAgICAgICAgICAgICAgICAgIHNob3dhcnJvdz1UUlVFLCBhcnJvd2hlYWQ9NCwgYXJyb3dzaXplPS41LCBhcnJvd2NvbG9yPSd3aGl0ZScsIGF4PS04MCwgYXk9MzAsCiAgICAgICAgICAgICAgICAgIGZvbnQ9bGlzdChjb2xvciA9ICcjODFjY2MyJywgZmFtaWx5PSdoZWx2ZXRpY2EnLCBzaXplID0gMTQpKSAlPiUKCiAgIyBBZGRpbmcgYW5kIHBvc2l0aW9uaW5nIHBsb3QgdGl0bGUKICBsYXlvdXQodGl0bGU9IkdEIG9wdGltaXphdGlvbiBvZiB0aGUgcGVha3MgZnVuY3Rpb24gKEYyKSIsIG1hcmdpbj1saXN0KGw9MTI1LCByPTAsIHQ9NjAsIGI9NjApKQoKIyBEaXNwbGF5IHRoZSBjb250b3VyIHBsb3QKZGl2KEYyLmdyYWRpZW50LmNvbnRvdXIsIGFsaWduPSJjZW50ZXIiKQpgYGAKClRlcm1pbmF0aW9uIHJlYXNvbiBhbmQgbnVtYmVyIG9mIGl0ZXJhdGlvbnM6CmBgYHtyfQpjYXQoc3ByaW50ZigiVGVybWluYXRpb24gcmVhc29uOiAlc1xuTnVtYmVyIG9mIGl0ZXJhdGlvbnM6ICVzIiwgRjIuZ3JhZGllbnQucmVzdWx0c1sxXSwgRjIuZ3JhZGllbnQucmVzdWx0c1syXSkpCmBgYAoKQmVuY2htYXJrczoKYGBge3J9CnByaW50KEYyLmdyYWRpZW50LnRpbWUpCmBgYAoKIyMjIENvb3JkaW5hdGUgZGVzY2VudAoKR3JhZGllbnQtYmFzZWQgY29vcmRpbmF0ZSBkZXNjZW50IGlzIGEgc2ltaWxhciBtZXRob2Qgb2Ygb3B0aW1pemF0aW9uIHRvIGdyYWRpZW50IGRlc2NlbnQsIGFzIGVhY2ggaXRlcmF0aW9uIHN0aWxsIHVwZGF0ZXMgdGhlIHBvc2l0aW9uIGJ5IG1vdmluZyAoYnkgYSBzdGVwIHNpemUgJFxldGEkKSBpbiB0aGUgZGlyZWN0aW9uIG9mIHN0ZWVwZXN0IGRlc2NlbnQuCgpIb3dldmVyLCB0aGUgbWFpbiBkaWZmZXJlbmNlIHdpdGggY29vcmRpbmF0ZSBkZXNjZW50IGlzIHRoYXQgd2Ugb3B0aW1pemUgb25lIGNvb3JkaW5hdGUgYXQgYSB0aW1lLS0tZXNzZW50aWFsbHkgc29sdmluZyAkZCQgdW5pdmFyaWF0ZSBvcHRpbWl6YXRpb24gcHJvYmxlbXMgKGlmIHRoZSBmdW5jdGlvbiAkRiQgaXMgJGQkLXZhcmlhdGUpLiBUaGUgb3B0aW1pemF0aW9uIHBhdGhzIGZyb20gdGhlc2Ugc3ViLXByb2JsZW1zIGFyZSB0aGVuIGNvbWJpbmVkIHRvIGZvcm0gYSBzb2x1dGlvbiB0byB0aGUgb3JpZ2luYWwgb3B0aW1pemF0aW9uIHByb2JsZW0uCgpGb3IgYSBzaW5nbGUgY29vcmRpbmF0ZSAkaSQsIHRoZSBpdGVyYXRpdmUgdXBkYXRlIGZvcm11bGEgaXMgZ2l2ZW4gYnk6CiQkCnhfe2krMX0gXGxlZnRhcnJvdyB4X2kgLSBcZXRhIFxmcmFje1xwYXJ0aWFsfXtccGFydGlhbCB4X2l9RihcbWF0aGJme3h9KQokJAoKV2UgZGVmaW5lIHRoZSBjb29yZGluYXRlIGRlc2NlbnQgYWxnb3JpdGhtIHJlY3Vyc2l2ZWx5IGFzOgpgYGB7cn0KIyBDb29yZGluYXRlIGRlc2NlbnQgKHJlY3Vyc2l2ZSBpbXBsZW1lbnRhdGlvbikKIwojIFBhcmFtZXRlcnM6CiMgICB4OiBUaGUgeC1jb29yZGluYXRlIGF0IHRoZSBjdXJyZW50IHBvc2l0aW9uCiMgICB5OiBUaGUgeS1jb29yZGluYXRlIGF0IHRoZSBjdXJyZW50IHBvc2l0aW9uCiMgICBmaXhlZDogV2hpY2ggY29vcmRpbmF0ZSByZW1haW5zIGZpeGVkICgxIC0+IHgsIDIgLT4geSkgd2Ugb3B0aW1pemUgdGhlIG5vbi1maXhlZCBjb29yZGluYXRlCiMgICBGVU46IFRoZSBncmFkaWVudCB2ZWN0b3IgZm9yIHRoZSBmdW5jdGlvbiBiZWluZyBvcHRpbWl6ZWQKIyAgIGl0ZXJhdGlvbnM6IFRoZSBudW1iZXIgb2YgaXRlcmF0aW9ucyAoc2hvdWxkIHN0YXJ0IGF0IDEpCiMgICBtaW5pbXVtOiBUaGUgYWN0dWFsIG1pbmltdW0gb2YgdGhlIGZ1bmN0aW9uCiMKIyBSZXR1cm5zOgojICAgQSB0dXBsZSBjb25zaXN0aW5nIG9mICh0ZXJtaW5hdGlvbiByZWFzb24sIGl0ZXJhdGlvbnMpLgojCmNvb3JkaW5hdGUuZGVzY2VudCA8LSBmdW5jdGlvbih4LCB5LCBmaXhlZCwgRlVOLCBpdGVyYXRpb25zLCBtaW5pbXVtKSB7CiAgIyBDaGVjayBmb3IgbWF4aW11bSBpdGVyYXRpb25zCiAgaWYoaXRlcmF0aW9ucyA+IG1heF9pdGVyYXRpb25zKSByZXR1cm4oYygiTWF4aW11bSBpdGVyYXRpb25zIHJlYWNoZWQiLCBpdGVyYXRpb25zLTEpKQoKICAjIE9wdGltaXppbmcgeCBjb29yZGluYXRlCiAgaWYgKGZpeGVkID09IDIpIHsKICAgICMgQ2hlY2sgZm9yIGNvbnZlcmdlbmNlCiAgICBpZihkaXN0KHJiaW5kKHgsIG1pbmltdW1bMV0pKSA8PSBlcHNpbG9uKSByZXR1cm4oYygiQ29udmVyZ2VkIiwgaXRlcmF0aW9ucy0xKSkKCiAgICAjIEFkZCBzdGFydGluZyBjb29yZGluYXRlIHRvIHBhdGggaWYgaXQgaXMgdGhlIGZpcnN0IGl0ZXJhdGlvbgogICAgaWYoaXRlcmF0aW9ucyA9PSAxKSBwYXRoW1sxXV0gPDwtIHgKCiAgICAjIE1ha2UgYW4gdXBkYXRlIHRvIHRoZSBjdXJyZW50IGNvb3JkaW5hdGUKICAgIHVwZGF0ZWQueCA8LSB4IC0gcmF0ZSAqIEZVTih4LCB5KVsxXQoKICAgICMgSW5jcmVtZW50IGl0ZXJhdGlvbnMgYW5kIHN0b3JlIHVwZGF0ZWQgcG9zaXRpb24gaW4gYHBhdGhgIHZhcmlhYmxlCiAgICBpdGVyYXRpb25zIDwtIGl0ZXJhdGlvbnMgKyAxCiAgICBwYXRoW1tpdGVyYXRpb25zXV0gPDwtIHVwZGF0ZWQueAoKICAgICMgTWFrZSB1cGRhdGVzIHJlY3Vyc2l2ZWx5CiAgICBjb29yZGluYXRlLmRlc2NlbnQodXBkYXRlZC54LCB5LCBmaXhlZD0yLCBGVU4sIGl0ZXJhdGlvbnMsIG1pbmltdW0pCiAgfQoKICAjIE9wdGltaXppbmcgeSBjb29yZGluYXRlCiAgZWxzZSBpZiAoZml4ZWQgPT0gMSkgewogICAgIyBDaGVjayBmb3IgY29udmVyZ2VuY2UKICAgIGlmKGRpc3QocmJpbmQoeSwgbWluaW11bVsyXSkpIDw9IGVwc2lsb24pIHJldHVybihjKCJDb252ZXJnZWQiLCBpdGVyYXRpb25zLTEpKQoKICAgICMgQWRkIHN0YXJ0aW5nIGNvb3JkaW5hdGUgdG8gcGF0aCBpZiBpdCBpcyB0aGUgZmlyc3QgaXRlcmF0aW9uCiAgICBpZihpdGVyYXRpb25zID09IDEpIHBhdGhbWzFdXSA8PC0geQoKICAgICMgTWFrZSBhbiB1cGRhdGUgdG8gdGhlIGN1cnJlbnQgY29vcmRpbmF0ZQogICAgdXBkYXRlZC55IDwtIHkgLSByYXRlICogRlVOKHgsIHkpWzJdCgogICAgIyBJbmNyZW1lbnQgaXRlcmF0aW9ucyBhbmQgc3RvcmUgdXBkYXRlZCBwb3NpdGlvbiBpbiBgcGF0aGAgdmFyaWFibGUKICAgIGl0ZXJhdGlvbnMgPC0gaXRlcmF0aW9ucyArIDEKICAgIHBhdGhbW2l0ZXJhdGlvbnNdXSA8PC0gdXBkYXRlZC55CgogICAgIyBNYWtlIHVwZGF0ZXMgcmVjdXJzaXZlbHkKICAgIGNvb3JkaW5hdGUuZGVzY2VudCh4LCB1cGRhdGVkLnksIGZpeGVkPTEsIEZVTiwgaXRlcmF0aW9ucywgbWluaW11bSkKICB9Cn0KYGBgCgojIyMjIFRlc3Rpbmcgb24gdGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uCgojIyMjIyAkeCQtY29vcmRpbmF0ZSBvcHRpbWl6YXRpb24KCk9wdGltaXppbmcgdGhlICR4JC1jb29yZGluYXRlOgpgYGB7cn0KIyBSZXNldCBvcHRpbWl6YXRpb24gcGF0aApyZXNldF9wYXRoKCkKCiMgUnVuIHRpbWVkIHgtY29vcmRpbmF0ZSBkZXNjZW50CkYxLmNvb3JkaW5hdGUueC50aW1lIDwtIHByb2MudGltZSgpCkYxLmNvb3JkaW5hdGUueC5yZXN1bHRzIDwtIGNvb3JkaW5hdGUuZGVzY2VudChGMS5zdGFydFsxXSwgRjEuc3RhcnRbMl0sIDIsIEYxLmQsIDEsIEYxLm1pbmltdW0pCkYxLmNvb3JkaW5hdGUueC50aW1lIDwtIHByb2MudGltZSgpIC0gRjEuY29vcmRpbmF0ZS54LnRpbWUKCiMgVHJ1Y2F0ZSBOVUxMcyBpbiBvcHRpbWl6YXRpb24gcGF0aCBsaXN0CkYxLmNvb3JkaW5hdGUueC5wYXRoIDwtIEZpbHRlcihOZWdhdGUoaXMubnVsbCksIHBhdGgpCmBgYAoKVGVybWluYXRpb24gcmVhc29uIGFuZCBudW1iZXIgb2YgaXRlcmF0aW9ucyBmb3IgJHgkLWNvb3JkaW5hdGUgb3B0aW1pemF0aW9uOgpgYGB7cn0KY2F0KHNwcmludGYoIlRlcm1pbmF0aW9uIHJlYXNvbjogJXNcbk51bWJlciBvZiBpdGVyYXRpb25zOiAlcyIsIEYxLmNvb3JkaW5hdGUueC5yZXN1bHRzWzFdLCBGMS5jb29yZGluYXRlLngucmVzdWx0c1syXSkpCmBgYAoKQmVuY2htYXJrcyBmb3IgJHgkLWNvb3JkaW5hdGUgb3B0aW1pemF0aW9uOgpgYGB7cn0KcHJpbnQoRjEuY29vcmRpbmF0ZS54LnRpbWUpCmBgYAoKIyMjIyMgJHkkLWNvb3JkaW5hdGUgb3B0aW1pemF0aW9uCgpPcHRpbWl6aW5nIHRoZSAkeSQtY29vcmRpbmF0ZToKYGBge3J9CiMgUmVzZXQgb3B0aW1pemF0aW9uIHBhdGggZnJvbSB4IGNvb3JkaW5hdGUKcmVzZXRfcGF0aCgpCgojIFJ1biB0aW1lZCB5LWNvb3JkaW5hdGUgZGVzY2VudApGMS5jb29yZGluYXRlLnkudGltZSA8LSBwcm9jLnRpbWUoKQpGMS5jb29yZGluYXRlLnkucmVzdWx0cyA8LSBjb29yZGluYXRlLmRlc2NlbnQoRjEuc3RhcnRbMV0sIEYxLnN0YXJ0WzJdLCAxLCBGMS5kLCAxLCBGMS5taW5pbXVtKQpGMS5jb29yZGluYXRlLnkudGltZSA8LSBwcm9jLnRpbWUoKSAtIEYxLmNvb3JkaW5hdGUueS50aW1lCgojIFRydWNhdGUgTlVMTHMgaW4gb3B0aW1pemF0aW9uIHBhdGggbGlzdApGMS5jb29yZGluYXRlLnkucGF0aCA8LSBGaWx0ZXIoTmVnYXRlKGlzLm51bGwpLCBwYXRoKQpgYGAKClRlcm1pbmF0aW9uIHJlYXNvbiBhbmQgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgZm9yICR5JC1jb29yZGluYXRlIG9wdGltaXphdGlvbjoKYGBge3J9CmNhdChzcHJpbnRmKCJUZXJtaW5hdGlvbiByZWFzb246ICVzXG5OdW1iZXIgb2YgaXRlcmF0aW9uczogJXMiLCBGMS5jb29yZGluYXRlLnkucmVzdWx0c1sxXSwgRjEuY29vcmRpbmF0ZS55LnJlc3VsdHNbMl0pKQpgYGAKCkJlbmNobWFya3MgZm9yICR5JC1jb29yZGluYXRlIG9wdGltaXphdGlvbjoKYGBge3J9CnByaW50KEYxLmNvb3JkaW5hdGUueS50aW1lKQpgYGAKCiMjIyMjIFNvbHZpbmcgdGhlIG9yaWdpbmFsIG9wdGltaXphdGlvbiBwcm9ibGVtCgpXZSBub3cgaGF2ZSB0byBjb21iaW5lIHRoZSBvcHRpbWl6YXRpb24gcGF0aHMgb2YgZWFjaCBjb29yZGluYXRlIGluIG9yZGVyIHRvIGZvcm0gYSBzaW5nbGUgb3B0aW1pemF0aW9uIHBhdGggZm9yIHRoZSBvcmlnaW5hbCBwcm9ibGVtLiBXZSBkbyB0aGlzIGJ5IGludGVybGVhdmluZyBlbGVtZW50cyBmcm9tIGVhY2ggY29vcmRpbmF0ZSdzIHBhdGgtLS1ob3dldmVyLCB3ZSBtdXN0IGFjY291bnQgZm9yIHRoZSBmYWN0IHRoYXQgb25lIGNvb3JkaW5hdGUgbWF5IGNvbnZlcmdlIGZhc3RlciB0aGFuIGFub3RoZXIgKGlmIGF0IGFsbCkuIEluIHRoaXMgY2FzZSwgd2UgZXh0ZW5kIHRoZSBvcHRpbWl6YXRpb24gcGF0aCBvZiB0aGUgY29vcmRpbmF0ZSB0aGF0IGNvbnZlcmdlZCBpbiBmZXdlciBpdGVyYXRpb25zLCBieSBpdHMgbGFzdCBlbnRyeSB1bnRpbCBpdHMgbGVuZ3RoIGlzIHRoZSBzYW1lIGFzIHRoYXQgb2YgdGhlIG90aGVyIGNvb3JkaW5hdGUncyBvcHRpbWl6YXRpb24gcGF0aC4KYGBge3J9CiMgQ2FsY3VsYXRlIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIG51bWJlciBvZiBpdGVyYXRpb25zIG9mIGJvdGggY29vcmRpbmF0ZXMnIG9wdGltaXphdGlvbiBwYXRocwpwYXRoX2RpZmZlcmVuY2UgPC0gbGVuZ3RoKEYxLmNvb3JkaW5hdGUueC5wYXRoKSAtIGxlbmd0aChGMS5jb29yZGluYXRlLnkucGF0aCkKCmlmIChwYXRoX2RpZmZlcmVuY2UgPiAwKSB7CiAgIyBJZiB0aGUgeC1jb29yZGluYXRlJ3Mgb3B0aW1pemF0aW9uIHBhdGggaGFkIG1vcmUgaXRlcmF0aW9ucywKICAjIGV4dGVuZCB0aGUgeS1jb29yZGluYXRlcyBvcHRpbWl6YXRpb24gcGF0aCBieSBpdHMgbGFzdCBlbnRyeQogICMgdW50aWwgaXQgaGFzIHRoZSBzYW1lIGxlbmd0aCBhcyB0aGUgeC1jb29yZGluYXRlJ3Mgb3B0aW1pemF0aW9uIHBhdGgKICBGMS5jb29yZGluYXRlLnkucGF0aCA8LSBjKEYxLmNvb3JkaW5hdGUueS5wYXRoLCByZXAodGFpbChGMS5jb29yZGluYXRlLnkucGF0aCwgbj0xKSwgYWJzKHBhdGhfZGlmZmVyZW5jZSkpKQp9IGVsc2UgewogICMgSWYgdGhlIHktY29vcmRpbmF0ZSdzIG9wdGltaXphdGlvbiBwYXRoIGhhZCBtb3JlIGl0ZXJhdGlvbnMsCiAgIyBleHRlbmQgdGhlIHgtY29vcmRpbmF0ZXMgb3B0aW1pemF0aW9uIHBhdGggYnkgaXRzIGxhc3QgZW50cnkKICAjIHVudGlsIGl0IGhhcyB0aGUgc2FtZSBsZW5ndGggYXMgdGhlIHktY29vcmRpbmF0ZSdzIG9wdGltaXphdGlvbiBwYXRoCiAgRjEuY29vcmRpbmF0ZS54LnBhdGggPC0gYyhGMS5jb29yZGluYXRlLngucGF0aCwgcmVwKHRhaWwoRjEuY29vcmRpbmF0ZS54LnBhdGgsIG49MSksIGFicyhwYXRoX2RpZmZlcmVuY2UpKSkKfQoKIyBJbml0aWFsaXplIGEgbmV3IGNvbWJpbmVkIG9wdGltaXphdGlvbiBwYXRoIHdpdGggdGhlIHN0YXJ0aW5nIHBvc2l0aW9uCnBhdGggPC0gdmVjdG9yKCJsaXN0IiwgbWF4X2l0ZXJhdGlvbnMqMikKcGF0aFtbMV1dIDwtIGMoRjEuY29vcmRpbmF0ZS54LnBhdGhbMV0sIEYxLmNvb3JkaW5hdGUueS5wYXRoWzFdKQoKIyBJbnRlcmxlYXZlIHRoZSBlbGVtZW50cyBvZiBib3RoIGNvb3JkaW5hdGUncyBvcHRpbWl6YXRpb24gcGF0aHMKIyB0byBmb3JtIGFuIG9wdGltaXphdGlvbiBwYXRoIGluIHRoZSBvcmlnaW5hbCB0d28tZGltZW5zaW9uYWwgeC15IHBsYW5lLgppIDwtIDIKaiA8LSAyCndoaWxlKGkgPD0gbGVuZ3RoKEYxLmNvb3JkaW5hdGUueC5wYXRoKSkgewogIHBhdGhbW2pdXSA8LSBjKEYxLmNvb3JkaW5hdGUueC5wYXRoW2ldLCBGMS5jb29yZGluYXRlLnkucGF0aFtpLTFdKQogIHBhdGhbW2orMV1dIDwtIGMoRjEuY29vcmRpbmF0ZS54LnBhdGhbaV0sIEYxLmNvb3JkaW5hdGUueS5wYXRoW2ldKQogIGkgPC0gaSArIDEKICBqIDwtIGogKyAyCn0KYGBgCgpQbG90dGluZyB0aGUgY29udG91ciBhbmQgcGF0aCBvZiB1cGRhdGVzOgpgYGB7ciwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KIyBDb252ZXJ0IHRoZSBgcGF0aGAgdmFyaWFibGUgdG8gYSBtYXRyaXgKcGF0aCA8LSBtYXRyaXgodW5saXN0KHBhdGgpLCBuY29sPTIsIGJ5cm93PVRSVUUpCgojIERpc3BsYXkgY29udG91ciBhbmQgb3B0aW1pemF0aW9uIHBhdGgKRjEuY29vcmRpbmF0ZS5jb250b3VyIDwtIHBsb3RfbHkoeD1+RjEueCwgeT1+RjEueSwgej1GMS56LCB3aWR0aD04MDAsIGhlaWdodD01MDAsCiAgICAgICAgICAgICAgICAgICAgICB0eXBlPSJjb250b3VyIiwgY29udG91cnM9bGlzdChzaG93bGFiZWxzID0gVFJVRSkpICU+JQoKICAjIEFkZCBvcHRpbWl6YXRpb24gcGF0aCB0cmFjZQogIGFkZF90cmFjZSh4PXBhdGhbLDFdLCB5PXBhdGhbLDJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iT3B0aW1pemF0aW9uIHBhdGgiLCBtb2RlPSJsaW5lIikgJT4lCgogICMgQWRkIGNyb3NzIGF0IHRhcmdldCBtaW5pbXVtIHBvc2l0aW9uCiAgYWRkX3RyYWNlKHg9RjEubWluaW11bVsxXSwgeT1GMS5taW5pbXVtWzJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iVGFyZ2V0IG1pbmltdW0iLAogICAgICAgICAgICBtb2RlPSJtYXJrZXJzIiwgbWFya2VyPWxpc3QoY29sb3I9IiM1ZWM0YTciLCBzaXplPTYsIHN5bWJvbD0ieCIpKSAlPiUKCiAgIyBBZGQgYXJyb3cgYW5kIGFubm90YXRpb24gZm9yIHN0YXJ0aW5nIHBvc2l0aW9uCiAgYWRkX2Fubm90YXRpb25zKHg9RjEuc3RhcnRbMV0sIHk9RjEuc3RhcnRbMl0sIHRleHQ9IlN0YXJ0IiwKICAgICAgICAgICAgICAgICAgc2hvd2Fycm93PVRSVUUsIGFycm93aGVhZD00LCBhcnJvd3NpemU9LjUsIGFycm93Y29sb3I9J3doaXRlJywgYXg9MzAsIGF5PS0zMCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZCBhcnJvdyBhbmQgYW5ub3RhdGlvbiBmb3IgdGFyZ2V0IG1pbmltdW0KICBhZGRfYW5ub3RhdGlvbnMoeD1GMS5taW5pbXVtWzFdLCB5PUYxLm1pbmltdW1bMl0sIHRleHQ9IlRhcmdldFxubWluaW11bSIsCiAgICAgICAgICAgICAgICAgIHNob3dhcnJvdz1UUlVFLCBhcnJvd2hlYWQ9NCwgYXJyb3dzaXplPS41LCBhcnJvd2NvbG9yPSd3aGl0ZScsIGF4PS04MCwgYXk9LTMwLAogICAgICAgICAgICAgICAgICBmb250PWxpc3QoY29sb3IgPSAnIzgxY2NjMicsIGZhbWlseT0naGVsdmV0aWNhJywgc2l6ZSA9IDE0KSkgJT4lCgogICMgQWRkaW5nIGFuZCBwb3NpdGlvbmluZyBwbG90IHRpdGxlCiAgbGF5b3V0KHRpdGxlPSJDRCBvcHRpbWl6YXRpb24gb2YgdGhlIHNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uIChGMSkiLCBtYXJnaW49bGlzdChsPTEyNSwgcj0wLCB0PTYwLCBiPTYwKSkKCiMgRGlzcGxheSB0aGUgY29udG91ciBwbG90CmRpdihGMS5jb29yZGluYXRlLmNvbnRvdXIsIGFsaWduPSJjZW50ZXIiKQpgYGAKCkluIG9yZGVyIHRvIGNvbXBhcmUgdGhlIHBlcmZvcm1hbmNlIG9mIGNvb3JkaW5hdGUgZGVzY2VudCB0byBncmFkaWVudCBkZXNjZW50LCB3ZSB3aWxsIGhhdmUgdG8gYWxzbyBjb21iaW5lIHRoZSBwZXJmb3JtYW5jZSBtZXRyaWNzIGZvciBhbGwgb2YgdGhlIGNvb3JkaW5hdGVzLiBGb3IgdGhlIHRvdGFsIHRpbWUgdGFrZW4gZm9yIGFsbCBjb29yZGluYXRlcyB0byBiZSBvcHRpbWl6ZWQsIHdlIGNhbiBzaW1wbHkgc3VtIHRoZSB0aW1lIHRha2VuIGZvciBlYWNoIG9uZS4gRm9yIHRoZSBudW1iZXIgb2YgaXRlcmF0aW9ucywgd2UgdGFrZSB0aGUgY29vcmRpbmF0ZSB3aXRoIHRoZSBoaWdoZXN0IG51bWJlciBvZiBpdGVyYXRpb25zOgpgYGB7cn0KIyBBZGRpbmcgdG9nZXRoZXIgdGhlIHRpbWUgdGFrZW4gZm9yIGVhY2ggY29vcmRpbmF0ZQpGMS5jb29yZGluYXRlLnRpbWUgPC0gRjEuY29vcmRpbmF0ZS54LnRpbWUgKyBGMS5jb29yZGluYXRlLnkudGltZQogIAojIFRha2UgdGhlIGNvb3JkaW5hdGUgd2hpY2ggaGFkIHRoZSBtYXhpbXVtIG51bWJlciBvZiBpdGVyYXRpb25zCkYxLmNvb3JkaW5hdGUuaXRlcmF0aW9ucyA8LSBtYXgoYXMubnVtZXJpYyhjKEYxLmNvb3JkaW5hdGUueC5yZXN1bHRzW1syXV0sIEYxLmNvb3JkaW5hdGUueS5yZXN1bHRzW1syXV0pKSkKYGBgCgojIyMjIFRlc3Rpbmcgb24gdGhlIFBlYWtzIGZ1bmN0aW9uCgojIyMjIyAkeCQtY29vcmRpbmF0ZSBvcHRpbWl6YXRpb24KCk9wdGltaXppbmcgdGhlICR4JC1jb29yZGluYXRlOgpgYGB7cn0KIyBSZXNldCBvcHRpbWl6YXRpb24gcGF0aApyZXNldF9wYXRoKCkKCiMgUnVuIHRpbWVkIHgtY29vcmRpbmF0ZSBkZXNjZW50CkYyLmNvb3JkaW5hdGUueC50aW1lIDwtIHByb2MudGltZSgpCkYyLmNvb3JkaW5hdGUueC5yZXN1bHRzIDwtIGNvb3JkaW5hdGUuZGVzY2VudChGMi5zdGFydFsxXSwgRjIuc3RhcnRbMl0sIDIsIEYyLmQsIDEsIEYyLm1pbmltdW0pCkYyLmNvb3JkaW5hdGUueC50aW1lIDwtIHByb2MudGltZSgpIC0gRjIuY29vcmRpbmF0ZS54LnRpbWUKCiMgVHJ1Y2F0ZSBOVUxMcyBpbiBvcHRpbWl6YXRpb24gcGF0aCBsaXN0CkYyLmNvb3JkaW5hdGUueC5wYXRoIDwtIEZpbHRlcihOZWdhdGUoaXMubnVsbCksIHBhdGgpCmBgYAoKVGVybWluYXRpb24gcmVhc29uIGFuZCBudW1iZXIgb2YgaXRlcmF0aW9ucyBmb3IgJHgkLWNvb3JkaW5hdGUgb3B0aW1pemF0aW9uOgpgYGB7cn0KY2F0KHNwcmludGYoIlRlcm1pbmF0aW9uIHJlYXNvbjogJXNcbk51bWJlciBvZiBpdGVyYXRpb25zOiAlcyIsIEYyLmNvb3JkaW5hdGUueC5yZXN1bHRzWzFdLCBGMi5jb29yZGluYXRlLngucmVzdWx0c1syXSkpCmBgYAoKQmVuY2htYXJrcyBmb3IgJHgkLWNvb3JkaW5hdGUgb3B0aW1pemF0aW9uOgpgYGB7cn0KcHJpbnQoRjIuY29vcmRpbmF0ZS54LnRpbWUpCmBgYAoKIyMjIyMgJHkkLWNvb3JkaW5hdGUgb3B0aW1pemF0aW9uCgpPcHRpbWl6aW5nIHRoZSAkeSQtY29vcmRpbmF0ZToKYGBge3J9CiMgUmVzZXQgb3B0aW1pemF0aW9uIHBhdGggZnJvbSB4IGNvb3JkaW5hdGUKcmVzZXRfcGF0aCgpCgojIFJ1biB0aW1lZCB5LWNvb3JkaW5hdGUgZGVzY2VudApGMi5jb29yZGluYXRlLnkudGltZSA8LSBwcm9jLnRpbWUoKQpGMi5jb29yZGluYXRlLnkucmVzdWx0cyA8LSBjb29yZGluYXRlLmRlc2NlbnQoRjIuc3RhcnRbMV0sIEYyLnN0YXJ0WzJdLCAxLCBGMi5kLCAxLCBGMi5taW5pbXVtKQpGMi5jb29yZGluYXRlLnkudGltZSA8LSBwcm9jLnRpbWUoKSAtIEYyLmNvb3JkaW5hdGUueS50aW1lCgojIFRydWNhdGUgTlVMTHMgaW4gb3B0aW1pemF0aW9uIHBhdGggbGlzdApGMi5jb29yZGluYXRlLnkucGF0aCA8LSBGaWx0ZXIoTmVnYXRlKGlzLm51bGwpLCBwYXRoKQpgYGAKClRlcm1pbmF0aW9uIHJlYXNvbiBhbmQgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgZm9yICR5JC1jb29yZGluYXRlIG9wdGltaXphdGlvbjoKYGBge3J9CmNhdChzcHJpbnRmKCJUZXJtaW5hdGlvbiByZWFzb246ICVzXG5OdW1iZXIgb2YgaXRlcmF0aW9uczogJXMiLCBGMi5jb29yZGluYXRlLnkucmVzdWx0c1sxXSwgRjIuY29vcmRpbmF0ZS55LnJlc3VsdHNbMl0pKQpgYGAKCkJlbmNobWFya3MgZm9yICR5JC1jb29yZGluYXRlIG9wdGltaXphdGlvbjoKYGBge3J9CnByaW50KEYyLmNvb3JkaW5hdGUueS50aW1lKQpgYGAKCiMjIyMjIFNvbHZpbmcgdGhlIG9yaWdpbmFsIG9wdGltaXphdGlvbiBwcm9ibGVtCgpDb21iaW5pbmcgb3B0aW1pemF0aW9uIHBhdGhzOgpgYGB7cn0KIyBDYWxjdWxhdGUgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgb2YgYm90aCBjb29yZGluYXRlJ3Mgb3B0aW1pemF0aW9uIHBhdGhzCnBhdGhfZGlmZmVyZW5jZSA8LSBsZW5ndGgoRjIuY29vcmRpbmF0ZS54LnBhdGgpIC0gbGVuZ3RoKEYyLmNvb3JkaW5hdGUueS5wYXRoKQoKIyBBY2NvdW50aW5nIGZvciBkaWZmZXJlbmNlIGluIGNvb3JkaW5hdGVzJyBudW1iZXIgb2YgaXRlcmF0aW9ucwppZiAocGF0aF9kaWZmZXJlbmNlID4gMCkgewogIEYyLmNvb3JkaW5hdGUueS5wYXRoIDwtIGMoRjIuY29vcmRpbmF0ZS55LnBhdGgsIHJlcCh0YWlsKEYyLmNvb3JkaW5hdGUueS5wYXRoLCBuPTEpLCBhYnMocGF0aF9kaWZmZXJlbmNlKSkpCn0gZWxzZSB7CiAgRjIuY29vcmRpbmF0ZS54LnBhdGggPC0gYyhGMi5jb29yZGluYXRlLngucGF0aCwgcmVwKHRhaWwoRjIuY29vcmRpbmF0ZS54LnBhdGgsIG49MSksIGFicyhwYXRoX2RpZmZlcmVuY2UpKSkKfQoKIyBJbml0aWFsaXplIGEgbmV3IGNvbWJpbmVkIG9wdGltaXphdGlvbiBwYXRoIHdpdGggdGhlIHN0YXJ0aW5nIHBvc2l0aW9uCnBhdGggPC0gdmVjdG9yKCJsaXN0IiwgbWF4X2l0ZXJhdGlvbnMqMikKcGF0aFtbMV1dIDwtIGMoRjIuY29vcmRpbmF0ZS54LnBhdGhbMV0sIEYyLmNvb3JkaW5hdGUueS5wYXRoWzFdKQoKIyBJbnRlcmxlYXZlIHRoZSBlbGVtZW50cyBvZiBib3RoIGNvb3JkaW5hdGUncyBvcHRpbWl6YXRpb24gcGF0aHMKIyB0byBmb3JtIGFuIG9wdGltaXphdGlvbiBwYXRoIGluIHRoZSBvcmlnaW5hbCB0d28tZGltZW5zaW9uYWwgeC15IHBsYW5lLgppIDwtIDIKaiA8LSAyCndoaWxlKGkgPD0gbGVuZ3RoKEYyLmNvb3JkaW5hdGUueC5wYXRoKSkgewogIHBhdGhbW2pdXSA8LSBjKEYyLmNvb3JkaW5hdGUueC5wYXRoW2ldLCBGMi5jb29yZGluYXRlLnkucGF0aFtpLTFdKQogIHBhdGhbW2orMV1dIDwtIGMoRjIuY29vcmRpbmF0ZS54LnBhdGhbaV0sIEYyLmNvb3JkaW5hdGUueS5wYXRoW2ldKQogIGkgPC0gaSArIDEKICBqIDwtIGogKyAyCn0KYGBgCgpQbG90dGluZyB0aGUgY29udG91ciBhbmQgcGF0aCBvZiB1cGRhdGVzOgpgYGB7ciwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KIyBDb252ZXJ0IHRoZSBgcGF0aGAgdmFyaWFibGUgdG8gYSBtYXRyaXgKcGF0aCA8LSBtYXRyaXgodW5saXN0KHBhdGgpLCBuY29sPTIsIGJ5cm93PVRSVUUpCgojIERpc3BsYXkgY29udG91ciBhbmQgb3B0aW1pemF0aW9uIHBhdGgKRjIuY29vcmRpbmF0ZS5jb250b3VyIDwtIHBsb3RfbHkoeD1+RjIueCwgeT1+RjIueSwgej1GMi56LCB3aWR0aD03MDAsIGhlaWdodD02MDAsCiAgICAgICAgICAgICAgICAgICAgICB0eXBlPSJjb250b3VyIiwgY29udG91cnM9bGlzdChzaG93bGFiZWxzID0gVFJVRSkpICU+JQoKICAjIEFkZCBvcHRpbWl6YXRpb24gcGF0aCB0cmFjZQogIGFkZF90cmFjZSh4PXBhdGhbLDFdLCB5PXBhdGhbLDJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iT3B0aW1pemF0aW9uIHBhdGgiLCBtb2RlPSJsaW5lIikgJT4lCgogICMgQWRkIGNyb3NzIGF0IHRhcmdldCBtaW5pbXVtIHBvc2l0aW9uCiAgYWRkX3RyYWNlKHg9RjIubWluaW11bVsxXSwgeT1GMi5taW5pbXVtWzJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iVGFyZ2V0IG1pbmltdW0iLAogICAgICAgICAgICBtb2RlPSJtYXJrZXJzIiwgbWFya2VyPWxpc3QoY29sb3I9IiM1ZWM0YTciLCBzaXplPTYsIHN5bWJvbD0ieCIpKSAlPiUKCiAgIyBBZGQgYXJyb3cgYW5kIGFubm90YXRpb24gZm9yIHN0YXJ0aW5nIHBvc2l0aW9uCiAgYWRkX2Fubm90YXRpb25zKHg9RjIuc3RhcnRbMV0sIHk9RjIuc3RhcnRbMl0sIHRleHQ9IlN0YXJ0IiwKICAgICAgICAgICAgICAgICAgc2hvd2Fycm93PVRSVUUsIGFycm93aGVhZD00LCBhcnJvd3NpemU9LjUsIGFycm93Y29sb3I9J3doaXRlJywgYXg9MzAsIGF5PS0zMCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZCBhcnJvdyBhbmQgYW5ub3RhdGlvbiBmb3IgdGFyZ2V0IG1pbmltdW0KICBhZGRfYW5ub3RhdGlvbnMoeD1GMi5taW5pbXVtWzFdLCB5PUYyLm1pbmltdW1bMl0sIHRleHQ9IlRhcmdldFxubWluaW11bSIsCiAgICAgICAgICAgICAgICAgIHNob3dhcnJvdz1UUlVFLCBhcnJvd2hlYWQ9NCwgYXJyb3dzaXplPS41LCBhcnJvd2NvbG9yPSd3aGl0ZScsIGF4PS04MCwgYXk9LTMwLAogICAgICAgICAgICAgICAgICBmb250PWxpc3QoY29sb3IgPSAnIzgxY2NjMicsIGZhbWlseT0naGVsdmV0aWNhJywgc2l6ZSA9IDE0KSkgJT4lCgogICMgQWRkaW5nIGFuZCBwb3NpdGlvbmluZyBwbG90IHRpdGxlCiAgbGF5b3V0KHRpdGxlPSJDRCBvcHRpbWl6YXRpb24gb2YgdGhlIHBlYWtzIGZ1bmN0aW9uIChGMikiLCBtYXJnaW49bGlzdChsPTEyNSwgcj0wLCB0PTYwLCBiPTYwKSkKCiMgRGlzcGxheSB0aGUgY29udG91ciBwbG90CmRpdihGMi5jb29yZGluYXRlLmNvbnRvdXIsIGFsaWduPSJjZW50ZXIiKQpgYGAKCkNvbWJpbmluZyB0aGUgcGVyZm9ybWFuY2UgbWV0cmljcyBmb3IgYm90aCBjb29yZGluYXRlczoKYGBge3J9CiMgQWRkaW5nIHRvZ2V0aGVyIHRoZSB0aW1lIHRha2VuIGZvciBlYWNoIGNvb3JkaW5hdGUKRjIuY29vcmRpbmF0ZS50aW1lIDwtIEYyLmNvb3JkaW5hdGUueC50aW1lICsgRjIuY29vcmRpbmF0ZS55LnRpbWUKICAKIyBUYWtlIHRoZSBjb29yZGluYXRlIHdoaWNoIGhhZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgaXRlcmF0aW9ucwpGMi5jb29yZGluYXRlLml0ZXJhdGlvbnMgPC0gbWF4KGFzLm51bWVyaWMoYyhGMi5jb29yZGluYXRlLngucmVzdWx0c1tbMl1dLCBGMi5jb29yZGluYXRlLnkucmVzdWx0c1tbMl1dKSkpCmBgYAoKIyBNZXRob2QgY29tcGFyaXNvbiBtZXRyaWNzCgojIyBCZW5jaG1hcmtzCgpQcmVwYXJpbmcgdGhlIGJlbmNobWFyayBjb21wYXJpc29uIHBsb3Q6CmBgYHtyLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIERhdGFmcmFtZSByZXByZXNlbnRpbmcgdGhlIGdyYWRpZW50IGFuZCBjb29yZGluYXRlIGRlc2NlbnQgYmVuY2htYXJrcyBvbiBGMQpGMS5iZW5jaG1hcmtzLmRmIDwtIGRhdGEuZnJhbWUoCiAgTWV0aG9kPXJlcChjKCJHcmFkaWVudCBkZXNjZW50IiwgIkNvb3JkaW5hdGUgZGVzY2VudCIpLCBlYWNoPTMpLAogIFR5cGU9YygiVXNlciIsICJTeXN0ZW0iLCAiRWxhcHNlZCAoVG90YWwpIiksCiAgVGltZT1yb3VuZChjKEYxLmdyYWRpZW50LnRpbWVbMTozXSwgRjEuY29vcmRpbmF0ZS50aW1lWzE6M10pLCBkaWdpdHM9MykKKQoKIyBHcm91cGVkIGJhciBwbG90IGZvciBjb21wYXJpc29uIG9mIHRoZSBiZW5jaG1hcmtzCkYxLmJlbmNobWFya3MucGxvdCA8LSBnZ3Bsb3QoZGF0YT1GMS5iZW5jaG1hcmtzLmRmLCBhZXMoeD1UeXBlLCB5PVRpbWUsIGZpbGw9TWV0aG9kKSkgKwogIGdlb21fYmFyKHN0YXQ9ImlkZW50aXR5IiwgcG9zaXRpb249ImRvZGdlIikgKwogIGdlb21fdGV4dChhZXMobGFiZWw9VGltZSksIGhqdXN0PTAuNSwgY29sb3I9ImJsYWNrIiwgc2l6ZT0yLjUsIHBvc2l0aW9uID0gcG9zaXRpb25fZG9kZ2UoMC45KSwgc2l6ZT0zLjUpICsKICBzY2FsZV9maWxsX21hbnVhbCgiTWV0aG9kIiwgdmFsdWVzPWMoIkdyYWRpZW50IGRlc2NlbnQiPSIjNzBiYWNmIiwgIkNvb3JkaW5hdGUgZGVzY2VudCI9IiNlYjY5NjMiKSkgKwogICNzY2FsZV9maWxsX2JyZXdlcihwYWxldHRlPSJQYWlyZWQiKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICBnZ3RpdGxlKCJGMSAoc2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24pIikgKwogIHRoZW1lKHBsb3QubWFyZ2luPXVuaXQoYygwLjUsIDAsIDAsIDApLCAiY20iKSkgKwogIGNvb3JkX2ZsaXAoKQoKIyBEYXRhZnJhbWUgcmVwcmVzZW50aW5nIHRoZSBncmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGJlbmNobWFya3Mgb24gRjIKRjIuYmVuY2htYXJrcy5kZiA8LSBkYXRhLmZyYW1lKAogIE1ldGhvZD1yZXAoYygiR3JhZGllbnQgZGVzY2VudCIsICJDb29yZGluYXRlIGRlc2NlbnQiKSwgZWFjaD0zKSwKICBUeXBlPWMoIlVzZXIiLCAiU3lzdGVtIiwgIkVsYXBzZWQgKFRvdGFsKSIpLAogIFRpbWU9cm91bmQoYyhGMi5ncmFkaWVudC50aW1lWzE6M10sIEYyLmNvb3JkaW5hdGUudGltZVsxOjNdKSwgZGlnaXRzPTMpCikKCiMgR3JvdXBlZCBiYXIgcGxvdCBmb3IgY29tcGFyaXNvbiBvZiB0aGUgYmVuY2htYXJrcwpGMi5iZW5jaG1hcmtzLnBsb3QgPC0gZ2dwbG90KGRhdGE9RjIuYmVuY2htYXJrcy5kZiwgYWVzKHg9VHlwZSwgeT1UaW1lLCBmaWxsPU1ldGhvZCkpICsKICBnZW9tX2JhcihzdGF0PSJpZGVudGl0eSIsIHBvc2l0aW9uPSJkb2RnZSIpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsPVRpbWUpLCBoanVzdD0wLjUsIGNvbG9yPSJibGFjayIsIHNpemU9Mi41LCBwb3NpdGlvbiA9IHBvc2l0aW9uX2RvZGdlKDAuOSksIHNpemU9My41KSArCiAgc2NhbGVfZmlsbF9tYW51YWwoIk1ldGhvZCIsIHZhbHVlcz1jKCJHcmFkaWVudCBkZXNjZW50Ij0iIzcwYmFjZiIsICJDb29yZGluYXRlIGRlc2NlbnQiPSIjZWI2OTYzIikpICsKICAjc2NhbGVfZmlsbF9icmV3ZXIocGFsZXR0ZT0iUGFpcmVkIikgKwogIHRoZW1lX21pbmltYWwoKSArCiAgZ2d0aXRsZSgiRjIgKHBlYWtzIGZ1bmN0aW9uKSIpICsKICBjb29yZF9mbGlwKCkKCiMgQXJyYW5naW5nIHRoZSBzdWJwbG90cwpiZW5jaG1hcmtzLnBsb3QgPC0gZ2dhcnJhbmdlKEYxLmJlbmNobWFya3MucGxvdCwgRjIuYmVuY2htYXJrcy5wbG90LCBucm93PTIsIGNvbW1vbi5sZWdlbmQ9VFJVRSwgbGVnZW5kPSJib3R0b20iKQpgYGAKClBsb3R0aW5nIHRoZSBiZW5jaG1hcmtzIGNvbXBhcmlzb246CmBgYHtyfQojIEFkZCBhIHBsb3QgdGl0bGUKYW5ub3RhdGVfZmlndXJlKGJlbmNobWFya3MucGxvdCwgCiAgICAgICAgICAgICAgICB0b3A9dGV4dF9ncm9iKCJHcmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGJlbmNobWFya3MiLCBzaXplPTE2LCBmYWNlPSJib2xkIikpCmBgYAoKQXMgZXhwbGFpbmVkIGVhcmxpZXIsIGNvb3JkaW5hdGUgZGVzY2VudCB0ZW5kcyB0byBvcHRpbWl6ZSBmYXN0ZXIgKGluIHRlcm1zIG9mIHJ1bi10aW1lKSB0aGFuIGdyYWRpZW50IGRlc2NlbnQuIERlc3BpdGUgdGhpcywgdGhlIGV4cGVyaW1lbnQgeWllbGRlZCBtaXhlZCByZXN1bHRzLCB3aXRoIGNvb3JkaW5hdGUgZGVzY2VudCBvcHRpbWl6aW5nICRGXzEkIHNpZ25pZmljYW50bHkgc2xvd2VyIHRoYW4gZ3JhZGllbnQgZGVzY2VudC4gSG93ZXZlciwgY29vcmRpbmF0ZSBkZXNjZW50IHNlZW1zIHRvIHBlcmZvcm0gYmV0dGVyIHdpdGggJEZfMiQsIGhhdmluZyBhIGZhc3RlciBydW4tdGltZSB0aGFuIGdyYWRpZW50IGRlc2NlbnQgaW4gdGhpcyBjYXNlLgoKVGhpcyB2YXJpZXR5IGluIHBlcmZvcm1hbmNlIG1ha2VzIGl0IGRpZmZpY3VsdCB0byBjb25jbHVkZSB0aGF0IG9uZSBvcHRpbWl6YXRpb24gbWV0aG9kIGlzIGJldHRlciB0aGFuIHRoZSBvdGhlciwgZXNwZWNpYWxseSBkdWUgdG8gdGhlIGZhY3QgdGhhdCB3ZSBkaWQgbm90IHBlcmZvcm0gcmVwZWF0ZWQgZXhwZXJpbWVudHMgb3IgdHJ5IG90aGVyIGZ1bmN0aW9ucywgb3Igb3RoZXIgY29tYmluYXRpb25zIG9mICRcZXRhJCwgJFxlcHNpbG9uJCBhbmQgc3RhcnRpbmcgcG9zaXRpb24uCgpNb3JlIGxpa2VseSwgY2VydGFpbiBpbXBsZW1lbnRhdGlvbiBjaG9pY2VzIGltcGFjdGVkIHRoZSBydW4tdGltZXMgb2YgdGhlc2Ugb3B0aW1pemF0aW9uIG1ldGhvZHMuIE5hbWVseSwgYm90aCBtZXRob2RzIHdlcmUgaW1wbGVtZW50ZWQgcmVjdXJzaXZlbHksIHdoaWNoIG1heSBsZWFkIHRvIGlzc3VlcyBzdWNoIGFzIGhhdmluZyB0byBkZWFsIHdpdGggdGhlIHJlY3Vyc2l2ZSBjYWxsIHN0YWNrIGZyYW1lLiBBZGRpdGlvbmFsbHksIHRoZSBnZW5lcmFsIGltcGxlbWVudGF0aW9uIG9mIHRoZSBvcHRpbWl6YXRpb24gbWV0aG9kcyB3ZXJlIHF1aXRlIG5vbi1zdGFuZGFyZC0tLWVzcGVjaWFsbHkgZm9yIGNvb3JkaW5hdGUgZGVzY2VudC4KCiMjIE51bWJlciBvZiBpdGVyYXRpb25zCgpQcmVwYXJpbmcgdGhlIGl0ZXJhdGlvbiBjb21wYXJpc29uIHBsb3Q6CmBgYHtyLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIERhdGFmcmFtZSByZXByZXNlbnRpbmcgdGhlIGdyYWRpZW50IGFuZCBjb29yZGluYXRlIGRlc2NlbnQgaXRlcmF0aW9ucyBvbiBGMQpGMS5pdGVyYXRpb25zLmRmIDwtIGRhdGEuZnJhbWUoCiAgTWV0aG9kPWMoIkdyYWRpZW50IGRlc2NlbnQiLCAiQ29vcmRpbmF0ZSBkZXNjZW50IiksCiAgSXRlcmF0aW9ucz1yb3VuZChhcy5udW1lcmljKGMoRjEuZ3JhZGllbnQucmVzdWx0c1tbMl1dLCBGMS5jb29yZGluYXRlLml0ZXJhdGlvbnMpKSkKKQoKIyBCYXIgcGxvdCBmb3IgY29tcGFyaXNvbiBvZiBpdGVyYXRpb25zCkYxLml0ZXJhdGlvbnMucGxvdCA8LSBnZ3Bsb3QoZGF0YT1GMS5pdGVyYXRpb25zLmRmLCBhZXMoeD1NZXRob2QsIHk9SXRlcmF0aW9ucywgZmlsbD1NZXRob2QpKSArCiAgZ2VvbV9iYXIoc3RhdD0iaWRlbnRpdHkiLCBwb3NpdGlvbj0iZG9kZ2UiKSArCiAgc2NhbGVfZmlsbF9tYW51YWwoIk1ldGhvZCIsIHZhbHVlcz1jKCJHcmFkaWVudCBkZXNjZW50Ij0iIzcwYmFjZiIsICJDb29yZGluYXRlIGRlc2NlbnQiPSIjZWI2OTYzIikpICsKICAjc2NhbGVfZmlsbF9icmV3ZXIocGFsZXR0ZT0iUGFpcmVkIikgKwogIGdlb21fdGV4dChhZXMobGFiZWw9SXRlcmF0aW9ucyksIGhqdXN0PTMsIGNvbG9yPSJ3aGl0ZSIsIHNpemU9NCwgcG9zaXRpb24gPSBwb3NpdGlvbl9kb2RnZSgwLjkpLCBzaXplPTMuNSkgKwogIHNjYWxlX3lfY29udGludW91cyhicmVha3M9ZnVuY3Rpb24oeCkgdW5pcXVlKGZsb29yKHByZXR0eShzZXEoMCwgKG1heCh4KSArIDEpICogMS4xKSkpKSkgKyAKICB0aGVtZV9taW5pbWFsKCkgKwogIHRoZW1lKGF4aXMudGV4dC55ID0gZWxlbWVudF9ibGFuaygpLCBheGlzLnRpY2tzLnkgPSBlbGVtZW50X2JsYW5rKCkpICsKICBnZ3RpdGxlKCJGMSAoc2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24pIikgKwogIHRoZW1lKHBsb3QubWFyZ2luPXVuaXQoYygwLjUsIDAsIDAsIDApLCAiY20iKSkgKwogIGNvb3JkX2ZsaXAoKQoKIyBEYXRhZnJhbWUgcmVwcmVzZW50aW5nIHRoZSBncmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGl0ZXJhdGlvbnMgb24gRjIKRjIuaXRlcmF0aW9ucy5kZiA8LSBkYXRhLmZyYW1lKAogIE1ldGhvZD1jKCJHcmFkaWVudCBkZXNjZW50IiwgIkNvb3JkaW5hdGUgZGVzY2VudCIpLAogIEl0ZXJhdGlvbnM9cm91bmQoYXMubnVtZXJpYyhjKEYyLmdyYWRpZW50LnJlc3VsdHNbWzJdXSwgRjIuY29vcmRpbmF0ZS5pdGVyYXRpb25zKSkpCikKCiMgQmFyIHBsb3QgZm9yIGNvbXBhcmlzb24gb2YgaXRlcmF0aW9ucwpGMi5pdGVyYXRpb25zLnBsb3QgPC0gZ2dwbG90KGRhdGE9RjIuaXRlcmF0aW9ucy5kZiwgYWVzKHg9TWV0aG9kLCB5PUl0ZXJhdGlvbnMsIGZpbGw9TWV0aG9kKSkgKwogIGdlb21fYmFyKHN0YXQ9ImlkZW50aXR5IiwgcG9zaXRpb249ImRvZGdlIikgKwogIHNjYWxlX2ZpbGxfbWFudWFsKCJNZXRob2QiLCB2YWx1ZXM9YygiR3JhZGllbnQgZGVzY2VudCI9IiM3MGJhY2YiLCAiQ29vcmRpbmF0ZSBkZXNjZW50Ij0iI2ViNjk2MyIpKSArCiAgI3NjYWxlX2ZpbGxfYnJld2VyKHBhbGV0dGU9IlBhaXJlZCIpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsPUl0ZXJhdGlvbnMpLCBoanVzdD0zLCBjb2xvcj0id2hpdGUiLCBzaXplPTQsIHBvc2l0aW9uID0gcG9zaXRpb25fZG9kZ2UoMC45KSwgc2l6ZT0zLjUpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoYnJlYWtzPWZ1bmN0aW9uKHgpIHVuaXF1ZShmbG9vcihwcmV0dHkoc2VxKDAsIChtYXgoeCkgKyAxKSAqIDEuMSkpKSkpICsgCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZShheGlzLnRleHQueSA9IGVsZW1lbnRfYmxhbmsoKSwgYXhpcy50aWNrcy55ID0gZWxlbWVudF9ibGFuaygpKSArCiAgZ2d0aXRsZSgiRjIgKHBlYWtzIGZ1bmN0aW9uKSIpICsKICBjb29yZF9mbGlwKCkKCiMgQXJyYW5naW5nIHRoZSBzdWJwbG90cwppdGVyYXRpb25zLnBsb3QgPC0gZ2dhcnJhbmdlKEYxLml0ZXJhdGlvbnMucGxvdCwgRjIuaXRlcmF0aW9ucy5wbG90LCBucm93PTIsIGNvbW1vbi5sZWdlbmQ9VFJVRSwgbGVnZW5kPSJib3R0b20iKQpgYGAKClBsb3R0aW5nIHRoZSBpdGVyYXRpb25zIGNvbXBhcmlzb246CmBgYHtyfQojIEFkZCBhIHBsb3QgdGl0bGUKYW5ub3RhdGVfZmlndXJlKGl0ZXJhdGlvbnMucGxvdCwgCiAgICAgICAgICAgICAgICB0b3A9dGV4dF9ncm9iKCJHcmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGl0ZXJhdGlvbnMiLCBzaXplPTE2LCBmYWNlPSJib2xkIikpCmBgYAoKVW5saWtlIGJlbmNobWFya3MsIHRoZSBudW1iZXIgb2YgaXRlcmF0aW9ucyB0aGF0IGVhY2ggb2YgdGhlc2Ugb3B0aW1pemF0aW9uIG1ldGhvZCB0YWtlcyB0byBjb252ZXJnZSAoaWYgaXQgZG9lcyBjb252ZXJnZSkgZG9lcyBub3QgdmFyeSBwZXIgZXhwZXJpbWVudC0tLWl0IHdpbGwgbmV2ZXIgY2hhbmdlIHVubGVzcyB3ZSBjaGFuZ2UgJFxldGEkLCAkXGVwc2lsb24kIG9yIHRoZSBzdGFydGluZyBwb3NpdGlvbiwgd2hpY2ggd2UgZGlkbid0LiBGb3IgdGhpcyByZWFzb24sIHJlcGVhdGVkIGV4cGVyaW1lbnRzIGFyZSBub3QgYXMgbmVjZXNzYXJ5IGFzIHRoZXkgYXJlIGZvciBiZW5jaG1hcmtpbmcsIHdoZXJlIHRoZSB1bmNlcnRhaW50eSBvZiBDUFUgcmVzb3VyY2UgYWxsb2NhdGlvbiBldGMuIGlzIGVub3VnaCB0byB3YXJyYW50IHJlcGVhdGVkIGV4cGVyaW1lbnRzLiAKCkhvd2V2ZXIsIGl0IHN0aWxsIGlzbid0IGZhaXIgdG8gbWFrZSBhIGNvbmNyZXRlIGNvbmNsdXNpb24gZnJvbSB0aGVzZSByZXN1bHRzLCBzaW5jZSB3ZSB3b3VsZCBuZWVkIHRvIHRlc3QgdGhlIG9wdGltaXphdGlvbiBtZXRob2RzIG9uIGRpZmZlcmVudCBvYmplY3RpdmUgZnVuY3Rpb25zLCBkaWZmZXJlbnQgJFxldGEkLCAkXGVwc2lsb24kIGFuZCBzdGFydGluZyBwb3NpdGlvbnMuCgpOZXZlcnRoZWxlc3MsIGNvb3JkaW5hdGUgZGVzY2VudCBvcHRpbWl6ZWQgdGhlIG9iamVjdGl2ZSBmdW5jdGlvbiAkRl8xJCBpbiB0d28gZmV3ZXIgaXRlcmF0aW9ucyB0aGFuIGdyYWRpZW50IGRlc2NlbnQuIEhvd2V2ZXIsIGZvciAkRl8yJCwgYm90aCBvcHRpbWl6YXRpb24gbWV0aG9kcyB0b29rIHRoZSBzYW1lIG51bWJlciBvZiBpdGVyYXRpb25zICgkOSQpIHRvIG9wdGltaXplIHRoZSBmdW5jdGlvbi4KCiMgUmVzb3VyY2VzCgpbXmwtYmZnc106IGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0xpbWl0ZWQtbWVtb3J5X0JGR1MKClteZ2xtbmV0XTogaHR0cHM6Ly93ZWIuc3RhbmZvcmQuZWR1L35oYXN0aWUvVEFMS1MvZ2xtbmV0LnBkZgoKW15jb29yZGluYXRlLWRlc2NlbnRdOiBodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9Db29yZGluYXRlX2Rlc2NlbnQKClteY2FtZWxdOiBodHRwczovL3d3dy5zZnUuY2EvfnNzdXJqYW5vL2NhbWVsNi5odG1sCgpbXnBlYWtzXTogaHR0cHM6Ly9hbC1yb29taS5vcmcvYmVuY2htYXJrcy91bmNvbnN0cmFpbmVkLzItZGltZW5zaW9ucy82My1wZWFrcy1mdW5jdGlvbgoKW15kZXJpdmF0aXZlLWZyZWVdOiBodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9EZXJpdmF0aXZlLWZyZWVfb3B0aW1pemF0aW9uCgpbXm5lbGRlci1tZWFkXTogaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTmVsZGVyJUUyJTgwJTkzTWVhZF9tZXRob2QKCltecHJvYy10aW1lXTogaHR0cHM6Ly9zdGF0LmV0aHouY2gvUi1tYW51YWwvUi1kZXZlbC9saWJyYXJ5L2Jhc2UvaHRtbC9wcm9jLnRpbWUuaHRtbAoKW15ncmFkaWVudC1kZXNjZW50XTogaHR0cHM6Ly9tbC1jaGVhdHNoZWV0LnJlYWR0aGVkb2NzLmlvL2VuL2xhdGVzdC9ncmFkaWVudF9kZXNjZW50Lmh0bWw=